Q - 水陆距离

HihoCoder - 1478

给定一个N x M的01矩阵，其中1表示陆地，0表示水域。对于每一个位置，求出它距离最近的水域的距离是多少。

矩阵中每个位置与它上下左右相邻的格子距离为1。

Input

第一行包含两个整数，N和M。

以下N行每行M个0或者1，代表地图。

数据保证至少有1块水域。

对于30%的数据，1 <= N, M <= 100

对于100%的数据，1 <= N, M <= 800

Output

输出N行，每行M个空格分隔的整数。每个整数表示该位置距离最近的水域的距离。

Sample Input

4 4  
0110  
1111  
1111  
0110

Sample Output

0 1 1 0  
1 2 2 1  
1 2 2 1  
0 1 1 0

思路：

​ 广搜。将所有水域 0 0 0全部放入队列并将离水域的距离设 0 0 0。接下来 b f s bfs bfs周围的所有未计算过Mindis的点，先被广搜到的点的状态就是离水域的最短距离，标记已经计算过并加入队列。

刚好一年前做过的题，现在比赛不会做，我真是太菜了

代码：

#include<queue>
#include<iostream>
#include<string.h>
#include<cstdio>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
const int maxn=1e3;
int n,m;//row:n colun:m
int grid[maxn][maxn];
int minDis[maxn][maxn];
struct node
{
    int x,y,s;
    node() {}
    node(int x,int y,int s)
    {
        this->x=x,this->y=y,this->s=s;
    }
};
int vis[maxn][maxn];
int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};
/* 把所有0放进队列，bfs其他点到0的距离，每个点最多进入一次。 */
queue<node>mmp;//
void bfs()//search minDis water
{
    while(!mmp.empty()){
        node mm=mmp.front();
        mmp.pop();
        for(int i=0;i<4;++i){
            int xx=mm.x+dir[i][0];
            int yy=mm.y+dir[i][1];
            if(xx>=0&&xx<n&&yy>=0&&yy<m&&vis[xx][yy]==-1){
                vis[xx][yy]=mm.s+1;
                mmp.push(node(xx,yy,mm.s+1));
            }
        }
    }
}
char s[maxn];
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        mset(vis,-1);
        for(int i=0; i<n; ++i)
        {
            scanf("%s",s);
            for(int j=0; j<m; ++j)
            {
                if(s[j]=='0'){
                    grid[i][j]=0;
                    vis[i][j]=0;
                    mmp.push(node(i,j,0));
                }
                else  grid[i][j]=1;
            }
        }
        bfs();
        for(int i=0; i<n; ++i)
            for(int j=0; j<m; ++j) printf("%d%c",vis[i][j],j==m-1?'\n':' ');
    }
    return 0;
}