容桂品牌网站建设,微信怎么推广自己的产品,下载一个百度时事新闻,手机制作h5的app免费题目#xff1a;
给定一个N x M的01矩阵#xff0c;其中1表示陆地#xff0c;0表示水域。对于每一个位置#xff0c;求出它距离最近的水域的距离是多少。
矩阵中每个位置与它上下左右相邻的格子距离为1。
Input
第一行包含两个整数#xff0c;N和M。
以下N行每行M个0…题目
给定一个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
分析
拿到题我最先想到的使用记忆化搜索但由于没有条件限制导致回路陷入死循环用book标记后交上去超时了下来补题求教后这道题用广搜。 1.利用队列先进先出的性质先将所有水域地点存入队列中走过的存入队列这样自然就求的点最近的水域的距离。
AC代码
#includestdio.h
#includestring.h
#includequeue
#includealgorithm
using namespace std;
const int M8e210;
int n,m;
char s[M][M];
int dp[M][M];
bool book[M][M];
int c[4][2] {0,1,0,-1,1,0,-1,0};
struct node
{int x,y,step;
};
void bfs()
{queuenodeq;node u,v;for(int i0; in; i)for(int j0; jm; j){if(s[i][j]0){book[i][j]1;u.xi;u.yj;u.step0;dp[i][j]0;q.push(u);}}while(!q.empty()){uq.front();q.pop();for(int i0; i4; i){int au.xc[i][0];int bu.yc[i][1];if(a0||b0||an||bm||book[a][b])continue;book[a][b]1;v.xa;v.yb;v.stepu.step1;dp[a][b]v.step;q.push(v);}}
}
int main()
{scanf(%d%d,n,m);for(int i0; in; i)scanf(%s,s[i]);bfs();for(int i0; in; i)for(int j0; jm; j)jm-1?printf(%d\n,dp[i][j]):printf(%d ,dp[i][j]);return 0;
}
