Untitled
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...