Untitled
unknown
plain_text
a year ago
2.8 kB
4
Indexable
#define _CRT_SECURE_NO_WARNINGS #include <iostream> using namespace std; int t, m, n, sr, sc, fire, water, out, mapkimcuong[15][15]; int map[15][15], mapout[15][15], firemap[15][15], visited1[15][15], visited2[15][15]; int r, c, front, rear, q[1000], Anwer, kimcuong, maxkc, check; int dx[] = { -1, 0, 1, 0 }; int dy[] = { 0, 1, 0, -1 }; struct Queue { void initQueue() { front = rear = -1; } int isEmpty() { if (front == rear) return 1; return 0; } void enQueue(int x) { rear++; q[rear] = x; } int deQueue() { if (!isEmpty()) { front++; return q[front]; } return -1; } }; void BFS(int x, int y) { Queue q1, q2; q1.enQueue(x); q2.enQueue(y); visited1[x][y] = 1; while (!q1.isEmpty()) { int u = q1.deQueue(); int v = q2.deQueue(); for (int k = 0; k < 4; k++) { int tx = u + dx[k]; int ty = v + dy[k]; if (tx > 0 && tx <= n && ty > 0 && ty <= m && !visited1[tx][ty] && map[tx][ty] != 1) { visited1[tx][ty] = 1; q1.enQueue(tx); q2.enQueue(ty); firemap[tx][ty] = firemap[u][v] + 1; } } } } void backtrack(int x, int y, int time) { visited2[x][y] = 1; if (map[x][y]) { check = 1; if (maxkc < kimcuong) maxkc = kimcuong; } for (int k = 0; k < 4; k++) { int tx = x + dx[k]; int ty = y + dy[k]; if (tx > 0 && tx <= n && ty > 0 && ty <= m && !visited2[tx][ty] && time < firemap[tx][ty]) { visited2[tx][ty] = 1; kimcuong += mapkimcuong[tx][ty]; backtrack(tx, ty, time + 1); visited2[tx][ty] = 0; kimcuong -= mapkimcuong[tx][ty]; } } } int main() { freopen("input.txt", "r", stdin); cin >> t; for (int tc = 1; tc <= t; tc++) { cin >> n >> m >> sr >> sc; cin >> fire; //goi lua for (int i = 0; i < fire; i++) { cin >> r >> c; firemap[r][c] = 1; } cin >> water; //goi nuoc for (int i = 0; i < water; i++) { cin >> r >> c; map[r][c] = 1; } cin >> out; for (int i = 0; i < out; i++) { cin >> r >> c; mapout[r][c] = 1; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> mapkimcuong[i][j]; visited1[i][j] = visited2[i][j] = 0; } } map[sr][sc] = 2; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (firemap[i][j] == 1) { BFS(i, j); } } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j ++) { cout << firemap[i][j] << " "; } cout << endl; } check = 0; maxkc = 0; backtrack(sr, sc, 0); if (check) { cout << tc << " " << maxkc << endl; } else cout << tc << " " << -1 << endl; } return 0; }
Editor is loading...
Leave a Comment