hihocoder1478 水陆距离

地址：http://hihocoder.com/problemset/problem/1478

题目：

水陆距离

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

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

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

输入

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

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

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

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

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

输出

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

样例输入

样例输出

0 1 1 0  
1 2 2 1  
1 2 2 1  
0 1 1 0
思路：bfs！把所有水域点先加入队列，然后按层bfs！

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 #define MP make_pair
 6 #define PB push_back
 7 typedef long long LL;
 8 typedef pair<int,int> PII;
 9 const double eps=1e-8;
10 const double pi=acos(-1.0);
11 const int K=1e6+7;
12 const int mod=1e9+7;
13 
14 int n,m,vis[808][808],dis[808][808];
15 char mp[808][808];
16 queue<PII >q;
17 int dx[]={0,0,-1,1},dy[]={-1,1,0,0};
18 bool check(int x,int y)
19 {
20     return x>=1&&x<=n&&y>=1&&y<=m;
21 }
22 void bfs(void)
23 {
24     while(q.size())
25     {
26         for(int i=1,sz=q.size();i<=sz;i++)
27         {
28             int x=q.front().first,y=q.front().second;
29             q.pop(),vis[x][y]=0;
30             for(int i=0;i<4;i++)
31             {
32                 int nx=x+dx[i],ny=y+dy[i];
33                 if(check(nx,ny)&&!vis[nx][ny]&&dis[nx][ny]>dis[x][y]+1)
34                     q.push(MP(nx,ny)),vis[nx][ny]=1,dis[nx][ny]=dis[x][y]+1;
35             }
36         }
37     }
38 }
39 int main(void)
40 {
41     memset(dis,0x3f3f3f3f,sizeof dis);
42     cin>>n>>m;
43     for(int i=1;i<=n;i++)
44     {
45         scanf("%s",&mp[i][1]);
46         for(int j=1;j<=m;j++)
47         if(mp[i][j]=='0')
48             dis[i][j]=0,q.push(MP(i,j));
49     }
50     bfs();
51     for(int i=1;i<=n;i++)
52     {
53         for(int j=1;j<=m;j++)
54         printf("%d ",dis[i][j]);
55         puts("");
56     }
57     return 0;
58 }