题目描述
给定一个N行M列的01矩阵A,A[i][j] 与 A[k][l] 之间的曼哈顿距离定义为:
$dist(A[i][j],A[k][l])=|i−k|+|j−l|$
输出一个N行M列的整数矩阵B,其中:
$B[i][j]=min_{1≤x≤N,1≤y≤M,A[x][y]}=dist(A[i][j],A[x][y])$
样例
输入样例:
3 4
0001
0011
0110
输出样例:
3 2 1 0
2 1 0 0
1 0 0 1
算法1
(bfs) $O(n)$
模板题
$B[i][j]=min_{1≤x≤N,1≤y≤M,A[x][y]}=dist(A[i][j],A[x][y])$ B[i][j]表示 A[i][j] 到 图中所有x, y且A[x][y] = 1的距离最小的值。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1010;
typedef pair<int, int> PII;
char a[N][N];
int dist[N][N];
int n, m;
queue<PII> q;
bool st[N][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int main(){
cin >> n >> m;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++) {
cin >> a[i][j];
if (a[i][j] == '1') {
q.push({i, j});
st[i][j] = 1;
dist[i][j] = 0;
}
}
while (q.size()){
auto t = q.front(); q.pop();
for (int i = 0; i < 4; i ++){
int x = t.first + dx[i], y = t.second + dy[i];
if (x >= 1 && x <= n && y >= 1 && y <= m && st[x][y] != 1){
dist[x][y] = dist[t.first][t.second] + 1;
q.push({x, y});
st[x][y] = 1;
}
}
}
for (int i = 1; i <= n; i ++){
for (int j = 1; j <= m; j ++){
printf("%d ", dist[i][j]);
}
puts("");
}
return 0;
}