Untitled
unknown
plain_text
a year ago
2.6 kB
3
Indexable
#include<iostream> using namespace std; int T, N, M, arr[50][50], visited[50][50]; int Answer, startX, startY, endX, endY; int dxr[4] = { 0, 0, 1, -1 }; int dyr[4] = { 1, -1, 0, 0 }; int dxc[2] = { 1, -1 }; int dyc[2] = { 0, 0 }; const int MAX = 10000; struct Queue { int rear, front; int queue[MAX]; Queue() { front = rear = -1; } void push(int value) { queue[++rear] = value; } int pop() { return queue[++front]; } bool isEmpty() { return front == rear; } }; bool isValid(int x, int y) { return x >= 0 && x < N && y >= 0 && y < M; } void bfs(int x, int y, int dist) { Queue q; q.push(x); q.push(y); q.push(dist); while (!q.isEmpty()) { int r = q.pop(); int c = q.pop(); int ndist = q.pop(); if (arr[r][c] == 3) { cout << ndist << " "; if (Answer > ndist) { Answer = ndist; } } // duyet hang ngang for (int i = 0; i < 4; i++) { int nx = r + dxr[i]; int ny = c + dyr[i]; if (isValid(nx, ny) && arr[nx][ny] == 1 && visited[nx][ny] == 0) { visited[nx][ny] = 1; q.push(nx); q.push(ny); q.push(ndist); } } // duyet hang doc for (int i = 0; i < 2; i++) { for (int k = 1; k <= N && k < Answer; k++) { int nx = r + k * dxc[i]; int ny = c + k * dyc[i]; if (isValid(nx, ny) && arr[nx][ny] == 1 && visited[nx][ny] == 0) { if (ndist < k - 1) { ndist = k - 1; } visited[nx][ny] = 1; q.push(nx); q.push(ny); q.push(ndist); break; } } } } } int main() { freopen("Mario.txt", "r", stdin); cin >> T; for (int tc = 1; tc <= T; tc++) { Answer = 999; cin >> N >> M; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cin >> arr[i][j]; if (arr[i][j] == 2) { startX = i; startY = j; } } } // Reset visited array for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { visited[i][j] = 0; } } bfs(startX, startY, 1); cout << "Case #" << tc << endl; cout << Answer << endl; } return 0; }
Editor is loading...
Leave a Comment