题目
给定一个 行 列的 矩阵 , 与 之间的曼哈顿距离定义为:
输出一个 行 列的整数矩阵 ,其中:
输入格式
第一行两个整数 。
接下来一个 行 列的 矩阵,数字之间没有空格。
输出格式
一个 行 列的矩阵 ,相邻两个整数之间用一个空格隔开。
数据范围
输入样例:
3 4
0001
0011
0110
输出样例:
3 2 1 0
2 1 0 0
1 0 0 1
解题
方法一:多源BFS
思路
在输入的过程中把所有 1
的位置记录下来,放入队列,然后按照上下左右四个方向一层一层BFS,并把搜索到的格子置为层数即可(搜索的过程中要标记已访问格子)。
代码
#include <iostream>
#include <limits>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1010, DIRS[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int n, m, g[N][N];
bool vis[N][N];
int main() {
scanf("%d%d", &n, &m);
queue<PII> que;
for (int i = 0; i < n; ++i) {
cin.ignore(numeric_limits<streamsize>::max(), '\n');
for (int j = 0; j < m; ++j) {
char c;
scanf("%c", &c);
int x = c - '0';
g[i][j] = x;
if (x == 1) {
que.push({i, j});
vis[i][j] = true;
}
}
}
int step = 0;
while (!que.empty()) {
int sz = que.size();
while (sz--) {
auto pr = que.front();
que.pop();
int x = pr.first, y = pr.second;
g[x][y] = step;
for (auto& DIR : DIRS) {
int nx = x + DIR[0], ny = y + DIR[1];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny]) {
vis[nx][ny] = true;
que.push({nx, ny});
}
}
}
++step;
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) printf("%d ", g[i][j]);
puts("");
}
return 0;
}
评论区