题目大意：

中山市的地图是一个n*n的矩阵，其中标号为1的表示商业区，标号为0的表示居民区。为了考察市内居民区与商业区的距离，并对此作出评估，市长希望你能够编写一个程序完成这一任务。

　　居民区i到商业区的距离指的是到距离它最近的商业区j的距离(|Xi-Xj|+|Yi-Yj|)，而你将统计的是对于城市中的每一个区域k，以它为中心，所有满足max(|Xk-Xm|,|Yk-Ym|)<=r的区域m到商业区距离之和。结果同样以n*n的矩阵形式输出。

思路：

70分： 

O(n⁴)直接暴力求解即可。

100分：

BFS

首先在读入的时候，若这个点是商业区，就先将它入队，之后跑一边BFS，求出每个居民区到商业区的距离（由于每个点只要访问1次，所以时间复杂度为O(n²)），之后用二维前缀和加速，输出每个位置的答案。总时间复杂度为O(tn²)。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5  6 const int dx[]={
   0,0,0,1,-1}; 7 const int dy[]={
   0,1,-1,0,0}; 8 int a[301][301],b[301][301],p[301][301],t,n,r,sum,head,tail,state[500001][3]; 9 10 int abs(int x)11 {12     if (x>0) return x;13     return -x;14 }15 16 int minn(int x)17 {18     return min(x,n);19 }20 21 int maxn(int x)22 {23     return max(x,0);24 }25 26 void bfs()27 {28     do29     {30         head++; 31         for (int i=1;i<=4;i++)  //向四个方向扩展32         {33             int xx=state[head][1]+dx[i];34             int yy=state[head][2]+dy[i];35             if (xx<0||xx>n||yy<0||yy>n||p[xx][yy]) continue;36             tail++;  //入队37             p[xx][yy]=1;38             state[tail][1]=xx;39             state[tail][2]=yy;40             b[xx][yy]=b[state[head][1]][state[head][2]]+1;41         }42     }43     while (head