Untitled

 avatar
unknown
plain_text
2 years ago
1.6 kB
5
Indexable
#include<iostream>

using namespace std;

int N, M;
int map[55][55];
int visit[55][55];

int ans;

int dR[4] = {0, -1, 0, 1};
int dC[4] = {-1, 0, 1, 0};

struct COOR {
	int r, c;
} Queue[2505];

int front, rear;

void init() {
	front = rear = -1;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			visit[i][j] = 0;
}

void push(int r, int c) {
	rear++;
	Queue[rear].r = r;
	Queue[rear].c = c;
}

COOR pop() {
	return Queue[++front];
}

bool isEmpty() {
	return front == rear;
}

int BFS(COOR start, COOR end) {
	init();

	visit[start.r][start.c] = 1;
	push(start.r, start.c);

	while (!isEmpty()) {
		COOR coor = pop();

		for (int i = 0; i < 4; i++) {
			int nC = coor.c + dC[i];
			for (int j = 1; j <= ans; j++) {
				int nR = coor.r;
				if (dR[i] != 0)
					nR += (j * dR[i]);

				if (nR >= 0 && nR < N && nC >= 0 && nC < M && !visit[nR][nC] && map[nR][nC]) {
					if (nR == end.r && nC == end.c) {
						return 1;
					}

					visit[nR][nC] = 1;
					push(nR, nC);
				}
			}
		}
	}

	return 0;
}

int main() {
	int T;
	//freopen("sample_input.txt", "r", stdin);
	cin >> T;

	for (int test_case = 1; test_case <= T; ++test_case) {
		cin >> N >> M;

		COOR start, end;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				cin >> map[i][j];
				if (map[i][j] == 2) {
					start.r = i; start.c = j;
				}

				if (map[i][j] == 3) {
					end.r = i; end.c = j;
				}
			}
		}

		ans = 1;

		while (!BFS(start, end)) {
			ans++;
		}

		cout << "Case #" << test_case << endl << ans << endl;
	}
	return 0;
}
Editor is loading...