2252: [2010Beijing wc]矩阵距离 

Time Limit: 10 Sec  Memory Limit: 256 MB

Submit: 563  Solved: 274

[ ][ ][ ]

Description

 

假设我们有矩阵,其元素值非零即1

a11…… a1m

…………….

an1…….anm

 

定义aij与akl之间的距离为D(aij,akl)=abs(i-k)+abs(j-L) 

Input

输入文件的第一行为两个整数，分别代表n和m。 

接下来的n行，第i行的第 j个字符代表aij

Output

输出包含N行，每行M个用空格分开的数字，其中第i行第J个数字代表

Min(D(aij,axy) 1<=x<=N 1<=y<m,且axy=1

Sample Input

3 4

0001

0011

0110

Sample Output

3 2 1 0

2 1 0 0

1 0 0 1

HINT

 

对于100%的数据，满足 0 <  m n <=1000

 

Source

 

题解：

广搜。

从1开始搜即可。

1 #include
      
        2 using namespace std; 3 #define MAXN 1010 4 #define INF 1e9 5 int fx[6]={
    0,0,1,-1}; 6 int fy[6]={
    1,-1,0,0}; 7 int dis[MAXN][MAXN],a[MAXN][MAXN],qx[MAXN*MAXN],qy[MAXN*MAXN]; 8 char s[MAXN][MAXN]; 9 bool vis[MAXN][MAXN];10 int main()11 {12     int n,m,i,j,wzx,wzy,head,tail,ux,uy,vx,vy;13     scanf("%d %d",&n,&m);14     for(i=1;i<=n;i++)scanf("\n%s",s[i]+1);15     wzx=0;wzy=0;16     memset(dis,0,sizeof(dis));17     head=0;tail=0;memset(vis,false,sizeof(vis));18     for(i=1;i<=n;i++)19     {20         for(j=1;j<=m;j++){dis[i][j]=INF;a[i][j]=s[i][j]-'0';if(a[i][j]==1){wzx=i,wzy=j;qx[++tail]=i;qy[tail]=j;vis[i][j]=true;dis[i][j]=0;}}21     }22     //memset(qx,0,sizeof(qx));23     //memset(qy,0,sizeof(qy));24     //memset(vis,false,sizeof(vis));25     //vis[wzx][wzy]=true;26     //head=0;tail=1;qx[tail]=wzx;qy[tail]=wzy;27     //dis[wzx][wzy]=0;28     while(head!=tail)29     {30         head++;if(head==1000010)head=0;31         ux=qx[head];32         uy=qy[head];33         for(i=0;i<=3;i++)34         {35             vx=ux+fx[i];36             vy=uy+fy[i];37             if(vx>=1&&vx<=n&&vy>=1&&vy<=m&&vis[vx][vy]==false)38             {39                 if(dis[vx][vy]>dis[ux][uy]+1)40                 {41                     vis[vx][vy]=true;42                     dis[vx][vy]=dis[ux][uy]+1;43                     tail++;if(tail==1000010)tail=0;44                     qx[tail]=vx;45                     qy[tail]=vy;46                 }47                 if(a[vx][vy]==1){dis[vx][vy]=0;vis[vx][vy]=true;}48             }49         }50         vis[ux][uy]=false;51     }52     for(i=1;i<=n;i++)53     {54         for(j=1;j<=m;j++)printf("%d ",dis[i][j]);55         printf("\n");56     }57     fclose(stdin);58     fclose(stdout);59     return 0;60 }