Bzoj 2252: [2010Beijing wc]矩阵距离 广搜

时间：2021-01-09 11:51:21

2252: [2010Beijing wc]矩阵距离

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 563  Solved: 274
[Submit][Status][Discuss]

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开始搜即可。
 #include<bits/stdc++.h>

 using namespace std;

 #define MAXN 1010

 #define INF 1e9

 int fx[]={,,,-};

 int fy[]={,-,,};

 int dis[MAXN][MAXN],a[MAXN][MAXN],qx[MAXN*MAXN],qy[MAXN*MAXN];

 char s[MAXN][MAXN];

 bool vis[MAXN][MAXN];

 int main()

 {

     int n,m,i,j,wzx,wzy,head,tail,ux,uy,vx,vy;

     scanf("%d %d",&n,&m);

     for(i=;i<=n;i++)scanf("\n%s",s[i]+);

     wzx=;wzy=;

     memset(dis,,sizeof(dis));

     head=;tail=;memset(vis,false,sizeof(vis));

     for(i=;i<=n;i++)

     {

         for(j=;j<=m;j++){dis[i][j]=INF;a[i][j]=s[i][j]-'';if(a[i][j]==){wzx=i,wzy=j;qx[++tail]=i;qy[tail]=j;vis[i][j]=true;dis[i][j]=;}}

     }

     //memset(qx,0,sizeof(qx));

     //memset(qy,0,sizeof(qy));

     //memset(vis,false,sizeof(vis));

     //vis[wzx][wzy]=true;

     //head=0;tail=1;qx[tail]=wzx;qy[tail]=wzy;

     //dis[wzx][wzy]=0;

     while(head!=tail)

     {

         head++;if(head==)head=;

         ux=qx[head];

         uy=qy[head];

         for(i=;i<=;i++)

         {

             vx=ux+fx[i];

             vy=uy+fy[i];

             if(vx>=&&vx<=n&&vy>=&&vy<=m&&vis[vx][vy]==false)

             {

                 if(dis[vx][vy]>dis[ux][uy]+)

                 {

                     vis[vx][vy]=true;

                     dis[vx][vy]=dis[ux][uy]+;

                     tail++;if(tail==)tail=;

                     qx[tail]=vx;

                     qy[tail]=vy;

                 }

                 if(a[vx][vy]==){dis[vx][vy]=;vis[vx][vy]=true;}

             }

         }

         vis[ux][uy]=false;

     }

     for(i=;i<=n;i++)

     {

         for(j=;j<=m;j++)printf("%d ",dis[i][j]);

         printf("\n");

     }

     fclose(stdin);

     fclose(stdout);

     return ;

 }

相关文章