侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 26 条评论

目 录CONTENT

文章目录

【BFS】矩阵距离

GabrielxD
2022-12-29 / 0 评论 / 0 点赞 / 308 阅读 / 620 字
温馨提示:
本文最后更新于 2022-12-29,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

173. 矩阵距离 - AcWing题库


给定一个 NNMM 列的 0101 矩阵 AAA[i][j]A[i][j]A[k][l]A[k][l] 之间的曼哈顿距离定义为:

dist(A[i][j],A[k][l])=ik+jldist(A[i][j],A[k][l])=|i-k|+|j-l|

输出一个 NNMM 列的整数矩阵 BB ,其中:

B[i][j]=min1xN,1yM,A[x][y]=1dist(A[i][j],A[x][y])B[i][j]=min_{1≤x≤N,1≤y≤M,A[x][y]=1}⁡{dist(A[i][j],A[x][y])}

输入格式

第一行两个整数 N,MN,M

接下来一个 NNMM 列的 0101 矩阵,数字之间没有空格。

输出格式

一个 NNMM 列的矩阵 BB ,相邻两个整数之间用一个空格隔开。

数据范围

1N,M10001 \le N,M \le 1000

输入样例:

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;
}
0

评论区