[jzoj 2137] 【GDKOI2004】城市统计 {bfs+前缀和}

题目

Description
　　中山市的地图是一个n*n的矩阵，其中标号为1的表示商业区，标号为0的表示居民区。为了考察市内居民区与商业区的距离，并对此作出评估，市长希望你能够编写一个程序完成这一任务。
　　居民区i到商业区的距离指的是到距离它最近的商业区j的距离(|Xi-Xj|+|Yi-Yj|)，而你将统计的是对于城市中的每一个区域k，以它为中心，所有满足max(|Xk-Xm|,|Yk-Ym|)<=r的区域m到商业区距离之和。结果同样以n*n的矩阵形式输出。
Input
第一行为t，表示以下有t组数据，每组数据之间以空行隔开，以下：
　　　第一行为n,r(1≤r<n≤150)$(1\le r<n\le 150)$ 　　
第二行起为一个n*n的矩阵。
Output
　　t组n*n的矩阵。每组用空行隔开

---

解题思路

---

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std; 
const int xx[4]={0,1,0,-1},yy[4]={1,0,-1,0}; 
struct node{
    int x,y; 
}t[10050];
int head,tail,tt,n,r,a[5051][5051];  
int main()
{
    scanf("%d",&tt); 
    while (tt--)
    {
        head=0,tail=0; 
        scanf("%d%d",&n,&r);  
        for (int i=1;i<=n;i++)
         for (int j=1;j<=n;j++)
         {
           scanf("%d",&a[i][j]);     
           if (a[i][j]==1) t[++tail].x=i,t[tail].y=j,a[i][j]=0; 
            else a[i][j]=1e9; 
         }
        do//bfs
        {
            head++; 
            for (int i=0;i<4;i++)
            {
                int xa=t[head].x+xx[i],ya=t[head].y+yy[i];
                if (a[xa][ya]==1e9||a[xa][ya]>a[t[head].x][t[head].y]+1) {
                    a[xa][ya]=a[t[head].x][t[head].y]+1; 
                    t[++tail].x=xa; t[tail].y=ya; 
                }
            }
        }while (head<tail); 
        for (int i=1;i<=n;i++)
         for (int j=1;j<=n;j++)
          a[i][j]=a[i][j]+a[i][j-1]+a[i-1][j]-a[i-1][j-1]; //前缀和
        for (int i=1;i<=n;printf("\n"),i++)
         for (int j=1;j<=n;j++)
         {
            int u=min(n,j+r),e=min(n,i+r),uu=max(0,j-r-1),ee=max(0,i-r-1); 
            printf("%d ",a[e][u]+a[ee][uu]-a[e][uu]-a[ee][u]); //输出答案（注意跟前面的前缀和相反）
         }
        printf("\n"); 
    }
}