Untitled

 avatar
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