给定一个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个空格分隔的整数。每个整数表示该位置距离最近的水域的距离。
样例输入 4 4 0110 1111 1111 0110 样例输出 0 1 1 0 1 2 2 1 1 2 2 1 0 1 1 0看到题目 就是觉得是搜索 因为水域的点会相对较少 所以可以从水域的点开始搜索 从0的点开始搜索
但是当时的想法是 因为有多个0的点 怕从一个0的点开始搜索之后 之后0的点搜索会产生影响 所以分别从每个0的点开始搜索 结果就TLE了 对每个点进行一次BFS 搜索的时间太长了
结束了 发现 从一个0的点开始搜索就够了 当前的点都是距离最小的 所以它下一步到达的点也会是最小的
#include <cstdio> #include <iostream> #include <cstring> #include <cmath> #include <algorithm> #include <string.h> #include <string> #include <vector> #include <queue> #define MEM(a,x) memset(a,x,sizeof a) #define eps 1e-8 #define MOD 10009 #define MAXN 10010 #define MAXM 100010 #define INF 99999999 #define ll __int64 #define bug cout<<"here"<<endl #define fread freopen("ceshi.txt","r",stdin) #define fwrite freopen("out.txt","w",stdout) using namespace std; int mp[1000][1000]; char mpp[1000][1000]; int dir[4][2]={{0,-1},{0,1},{-1,0},{1,0}}; int point[810][810]; int vis[810][810]; int n,m; struct node { int x,y,num; // node(int xx,int yy,int nn) // { // x=xx; y=yy; num=nn; // } }; node no[810][810]; //node no[1000][1000]; queue<node> que; queue<node> q2; void bfs(int x,int y) { node nnode; nnode.x=x; nnode.y=y; nnode.num=0; q2.push(nnode); while(!q2.empty()) { node q=q2.front(); q2.pop(); int qx=q.x,qy=q.y; for(int i=0;i<4;i++) { int px=qx+dir[i][0]; int py=qy+dir[i][1]; if(px<0||px>=n||py<0||py>=m||vis[px][py]==1||mp[px][py]==0) continue; if(no[px][py].num>no[qx][qy].num+1) { no[px][py].num=no[qx][qy].num+1; vis[px][py]=1; q2.push(no[px][py]); } } } } int main() { // fread; scanf("%d%d",&n,&m); for(int i=0;i<n;i++) { // for(int j=0;j<m;j++) // { // scanf("%d",&mp[i][j]); scanf("%s",mpp[i]); // } } for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { mp[i][j]=mpp[i][j]-'0'; no[i][j].x=i; no[i][j].y=j; if(mp[i][j]==0) { no[i][j].num=0; que.push(no[i][j]); // cout<<i<<" "<<j<<endl; } else no[i][j].num=2000; } } // for(int i=0;i<n;i++) // { // for(int j=0;j<m;j++) // cout<<mp[i][j]; // cout<<endl; // } // for(int i=0;i<n;i++) // { // for(int j=0;j<m;j++) // { // no[i][j].x=i; // no[i][j].y=j; // if(mp[i][j]==0) // { // no[i][j].num=0; // que.push(no[i][j]); cout<<i<<" "<<j<<endl; // } // else no[i][j].num=2000; // // } // } MEM(vis,0); while(!que.empty()) { node q=que.front(); que.pop(); int qx=q.x,qy=q.y; vis[qx][qy]=1; for(int i=0;i<4;i++) { int px=qx+dir[i][0]; int py=qy+dir[i][1]; if(px<0||px>=n||py<0||py>=m||vis[px][py]==1||mp[px][py]==0) continue; if(no[px][py].num>no[qx][qy].num+1) { no[px][py].num=no[qx][qy].num+1; vis[px][py]=1; que.push(no[px][py]); } } } while(!que.empty()) que.pop(); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(j) printf(" "); printf("%d",no[i][j].num); } puts(""); } return 0; }
