Untitled
unknown
plain_text
a year ago
1.9 kB
14
Indexable
#include<iostream> using namespace std; int T, N, M, arr[100][100], visited[100][100]; int Answer, startX, startY, endX, endY; int dxr[4] = { 0, 0}; int dyr[4] = { 1, -1}; 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 < 2; i++){ int nx = r + dxr[i]; int ny = c + dxr[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) { ndist = k; } 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; } } } bfs(startX, startY, 1); cout << "Case #" << tc << endl; cout << Answer << endl; } return 0; }
Editor is loading...
Leave a Comment