使用bfs
算法来优化 $O(N^4)$ 的暴力算法
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define dist pair <int, int>
using namespace std;
int dis[1010][1010];
char a[1010][1010];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i ++)
scanf ("%s", a[i] + 1);
queue <dist> q;
memset(dis, -1, sizeof dis);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
if (a[i][j] == '1')
dis[i][j] = 0;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
if (dis[i][j] == 0)
q.push(make_pair(i, j));
while (! q.empty())
{
auto f = q.front();
q.pop();
for (int i = 0; i < 4; i ++)
{
int nx = f.first + dx[i];
int ny = f.second + dy[i];
if (nx <= 0 || nx > n || ny <= 0 || ny > m)
continue;
if (dis[nx][ny] != -1)
continue;
dis[nx][ny] = dis[f.first][f.second] + 1;
q.push(make_pair(nx, ny));
}
}
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
printf ("%d%c", dis[i][j], (j == m) ? '\n' : ' ');
return 0;
}