題目：

給定一個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代碼：

#include<stdio.h> #include<string.h> #include<queue> #include<algorithm> using namespace std; const int M=8e2+10; 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() {queue<node>q;node u,v;for(int i=0; i<n; i++)for(int j=0; j<m; j++){if(s[i][j]=='0'){book[i][j]=1;u.x=i;u.y=j;u.step=0;dp[i][j]=0;q.push(u);}}while(!q.empty()){u=q.front();q.pop();for(int i=0; i<4; i++){int a=u.x+c[i][0];int b=u.y+c[i][1];if(a<0||b<0||a>=n||b>=m||book[a][b])continue;book[a][b]=1;v.x=a;v.y=b;v.step=u.step+1;dp[a][b]=v.step;q.push(v);}} } int main() {scanf("%d%d",&n,&m);for(int i=0; i<n; i++)scanf("%s",s[i]);bfs();for(int i=0; i<n; i++)for(int j=0; j<m; j++)j==m-1?printf("%d\n",dp[i][j]):printf("%d ",dp[i][j]);return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的G - 水陆距离 HihoCoder - 1478（广搜+队列先进先出性质）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。