mario_climb_chatnhiphan
//mario climb #include <iostream> using namespace std; int M, N; int xS, yS, xE, yE; int front, rear; int dx[] = {0,0,1,-1}; int dy[] = {1,-1,0,0}; int A[55][55]; int visit[55][55]; int ans; struct Node{ int r,c; }; Node queue[100000]; void enQueue(int x, int y){ Node node; node.r = x; node.c = y; rear++; queue[rear] = node; } Node deQueue(){ front++; return queue[front]; } void resetVisit(){ for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { visit[i][j] = 0; } } } int check(int k){ resetVisit(); front = rear = -1; enQueue(xS,yS); visit[xS][yS] = 1; while (front!=rear) { Node mid = deQueue(); if(mid.r == xE && mid.c == yE){ return 1; } for (int i = 2; i <= 3; i++) { for (int j = 1; j <= k; j++) { int tx = mid.r + dx[i] * j; int ty = mid.c + dy[i]; if (tx >= 0 && tx < M && ty >= 0 && ty < N && visit[tx][ty] == 0 && (A[tx][ty] == 1 || A[tx][ty] == 3)) { enQueue(tx,ty); visit[tx][ty] = 1; } } } for (int i = 0; i < 2; i++) { int tx = mid.r + dx[i]; int ty = mid.c + dy[i]; if (tx >= 0 && tx < M && ty >= 0 && ty < N && visit[tx][ty] == 0 && (A[tx][ty] == 1 || A[tx][ty] == 3)) { enQueue(tx,ty); visit[tx][ty] = 1; } } } return 0; } int fun(int s, int e){ int mid = s + (e - s)/2; if (check(mid-1) == 0 && check(mid) == 1) { return mid; } if(check(mid) == 1){ return fun(s,mid); }else { return fun(mid+1,e); } } int main(){ int tc, T; //freopen("input.txt", "r", stdin); cin>> T; for (tc = 1; tc <= T; tc++) { cin >> M >> N; ans = 0; for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { cin>> A[i][j]; if(A[i][j] == 2){ xS = i; yS = j; } if (A[i][j] == 3) { xE = i; yE = j; } } } ans = fun(1,50); cout<< "Case #" << tc <<endl; cout<< ans << endl; } return 0; }
Leave a Comment