Untitled
unknown
plain_text
9 months ago
2.6 kB
3
Indexable
#include <iostream> using namespace std; int T, n, m, xst, yst, map[5000][5000], visit[5000][5000]; int tmpx, tmpy, tx, ty, qx[10000000], qy[10000000], front, rear; int x2, y2, sp[5][2], t, dem, check, cnt1, cnt2, visitFull; void resetVisit() { for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { visit[i][j] = 0; } } } void initQueue() { front = rear = -1; } int isEmpty() { return front == rear; } void enQueue(int x, int y) { qx[++rear] = x; qy[rear] = y; } void deQueue(int& tmpx, int& tmpy) { tmpx = qx[++front]; tmpy = qy[front]; } int isValid() { return tx > 0 && tx <= n && ty > 0 && ty <= m && map[tx][ty] ==1; } int checkSpecial() { for (int i = 0; i < 4; i++) { if (!visit[sp[i][0]][sp[i][1]]) return 0; } return 1; } int dx[4] = { -1, 0, 1, 0 }; int dy[4] = { 0, 1, 0, -1 }; void BFS(int x, int y) { initQueue(); resetVisit(); visit[x][y] = 1; enQueue(x, y); while (!isEmpty()) { deQueue(tmpx, tmpy); for (int k = 0; k < 4; k++) { tx = tmpx + dx[k]; ty = tmpy + dy[k]; if (isValid()) { if (!visit[tx][ty] || (visit[tx][ty] && visit[tmpx][tmpy] + 1 < visit[tx][ty])) { visit[tx][ty] = visit[tmpx][tmpy] + 1; enQueue(tx, ty); } } } } } int main() { cin >> T; for (int tc = 1; tc <= T; tc++) { cnt1 = cnt2 = 0; t = -1; dem = 0; check = visitFull = 1; cin >> n >> m; cin >> xst >> yst; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> map[i][j]; if (map[i][j] == 2) { x2 = i; y2 = j; } } } //Logic //Tim 4 o xung quanh o special for (int k = 0; k < 4; k++) { int x22 = x2 + dx[k]; int y22 = y2 + dy[k]; if (x22 <= 0 || x22 > n || y22 <= 0 || y22 > m || map[x22][y22] != 1) { check = 0; break; } dem++; sp[++t][0] = x22; sp[t][1] = y22; } //Print cout << "Case #" << tc << endl; if (check) { BFS(xst, yst); for (int k = 0; k < 4; k++) { int x22 = x2 + dx[k]; int y22 = y2 + dy[k]; cnt1 = visit[x22][y22] > cnt1 ? visit[x22][y22] : cnt1; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (map[i][j] == 1 && !visit[i][j]) { visitFull = 0; break; } cnt2 = visit[i][j] > cnt2 ? visit[i][j] : cnt2; } } //cnt2--; if (visitFull) cout << cnt1 << " " << cnt2 << endl; else cout << cnt1 << " " << -1 << endl; } else { cout << -1 << " " << -1 << endl; } } return 0; }
Editor is loading...
Leave a Comment