【題解】Green Judge g070: E.傘兵

【題目敘述】http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=g070
【Tag】BFS

#include <iostream>
#include <queue>
using namespace std;
const int maxn = 105;
int risk[maxn][maxn];
int dr[] = {1, -1, 0, 0};
int dc[] = {0, 0, 1, -1};

struct Node {
    int r, c, v;
    Node (int _r, int _c, int _v) {
        r = _r;
        c = _c;
        v = _v;
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T, R, C, N, r, c, v;
    cin >> T;
    while (T--) {
        cin >> R >> C >> N;
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                risk[i][j] = 2e9;
            }
        }
        for (int i = 0; i < N; i++) {
            cin >> r >> c >> v;
            r--;
            c--;
            risk[r][c] = min(risk[r][c], v);
            queue <Node> q;
            q.push(Node(r, c, v));
            while (!q.empty()) {
                r = q.front().r;
                c = q.front().c;
                v = q.front().v;
                q.pop();
                for (int j = 0; j < 4; j++) {
                    int nr = r + dr[j];
                    int nc = c + dc[j];
                    if (nr >= 0 && nr < R && nc >= 0 && nc < C) {
                        if (v + 1 < risk[nr][nc]) {
                            q.push(Node(nr, nc, v+1));
                            risk[nr][nc] = v + 1;
                        }
                    }
                }
            }
        }
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                cout << risk[i][j] << " ";
            }
            cout << "\n";
        }
    }
    
    return 0;
}
分享本文 Share with friends