【題目敘述】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;
}