1032: 水陆距离
题目描述
给定一个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
思路
简简单单的 BFS，只是要注意的陆地到水的距离就是水到陆地的距离，对于所有水域同时开始 BFS，可以降低时间复杂度。若对于所有陆地都进行搜索，可能会超时。
#include<bits/stdc++.h>
using namespace std;
char a[810][810];
int vis[810][810];
int dir[4][2] = {
{
-1, 0}, {
1, 0}, {
0, -1}, {
0, 1}};
int ans[810][810];
typedef struct Node
{
int x, y, t;
}node;
int main()
{
int n, m, len;while(scanf("%d%d", &n, &m) != EOF) {
memset(vis, 0, sizeof(vis));memset(ans, 0, sizeof(ans));queue<node> q;for(int i = 0; i < n; i++){
scanf("%s", a[i]);for(int j = 0; j < m; j++)if(a[i][j] == '0'){
q.push({
i, j, 0});vis[i][j] = 1;} }node p;while(!q.empty()){
len = q.size();while(len--){
p = q.front();q.pop();for(int i = 0; i < 4; i++){
int x = p.x + dir[i][0], y = p.y + dir[i][1];if(x >= 0 && x < n && y >= 0 && y < m && !vis[x][y]){
q.push({
x, y, p.t + 1});ans[x][y] = p.t + 1;vis[x][y] = 1;}}}}for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++)printf("%d ", ans[i][j]);printf("\n");}}return 0;
}