AcWing 173. 矩阵距离

题目传送门

一、题意理解

二、实现代码

#include 

using namespace std;

#define x first
#define y second
typedef pair PII;
const int N = 1010, M = N * N;

int n, m;
char g[N][N];
PII q[M];
int dist[N][N];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

void bfs() {
    memset(dist, -1, sizeof dist);
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (g[i][j] == '1') {
                dist[i][j] = 0;
                q[++tt] = {i, j};
            }

    while (hh <= tt) {
        PII t = q[hh++];
        for (int i = 0; i < 4; i++) {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 1 || a > n || b < 1 || b > m) continue;
            if (dist[a][b] != -1) continue;

            dist[a][b] = dist[t.x][t.y] + 1;
            q[++tt] = {a, b};
        }
    }
}

int main() {
    //优化读入
    ios::sync_with_stdio(false);
    cin >> n >> m;
    //放过0行和0列
    for (int i = 1; i <= n; i++) cin >> g[i] + 1;
    //这个+1用的妙，一行行读入，每一行从下标1的列号开始

    bfs();

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            printf("%d ", dist[i][j]);
        puts("");
    }
    return 0;
}