解题思路:
找到水域开始搜,然后就像病毒扩散一样,距离永远是最低的
如果从每一个陆地开始BFS,就是每一次还要重新置零,效率就很低了。
#include<iostream> #include<algorithm> #include<cstring> #include<queue> using namespace std; const int maxn = 101; int n, m; char map[maxn][maxn]; int vist[maxn][maxn]; int End[maxn][maxn]; struct Node { int x, y, step; }; queue<Node> Q; Node zero; int dx[4] = { 0,0,-1,1 }; int dy[4] = { -1,1,0,0 }; void BFS() { Node now, next; while (!Q.empty()) { now = Q.front(); Q.pop(); for (int i = 0; i < 4; i++) { next.x = now.x + dx[i]; next.y = now.y + dy[i]; next.step = End[now.x][now.y] + 1; if (next.x >= 0 && next.x < n&&next.y >= 0 && next.y < m && !vist[next.x][next.y]) { End[next.x][next.y] = next.step; vist[next.x][next.y] = 1; Q.push(next); } } } } int main() { cin >> n >> m; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> map[i][j]; for(int i=0;i<n;i++) for (int j = 0; j < m; j++) { if (map[i][j] == '0') { zero.x = i; zero.y = j; Q.push(zero); vist[i][j] = 1; } } BFS(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) cout << End[i][j] << " "; cout << endl; } return 0; }
0.0分
1 人评分