Untitled
unknown
plain_text
2 years ago
1.3 kB
3
Indexable
#include<iostream> using namespace std; int M,N, h; int A[55][55]; int visit[55][55]; int x_st, y_st, x_end , y_end; int f=-1; int Qx[100000]; int Qy[100000]; int dx[4]= {1,-1,0,0}; int dy[4]= {0,0,1,-1}; void push(int x,int y) { f++; Qx[f] =x; Qy[f] =y; } void reset() { for(int i=1; i<= M; i++) { for(int j=1; j<=N; j++) { visit[i][j] =0; } } } void pop(int &x,int &y) { x= Qx[f]; y= Qy[f]; f--; } bool dfs(int x,int y,int h) { f=-1; push(x,y); visit[x][y] =1; while(f != -1) { pop(x,y); for(int i=1; i<=h; i++) { for(int j=0; j<4; j++) { int xx = x +i* dx[j]; int yy= y + dy[j]; if(visit[xx][yy] == 0 && xx>=1 && xx <=M && yy >=1 && yy <=N && A[xx][yy] != 0){ if(A[xx][yy] == 3) { return true; } push(xx,yy); visit[xx][yy] =1; } } } } return false; } int main() { int t; cin >> t; for(int stt=1; stt <=t; stt++) { cin >> M >> N; for(int i=1; i<= M; i++) { for(int j=1; j<=N; j++) { cin >> A[i][j]; if(A[i][j] ==2) { x_st = i; y_st = j;} } } ////////////////////////// int ans =0; for(int i=1; i<= N-1; i++){ reset(); if(dfs(x_st,y_st,i)){ ans = i; break; } } /////////////////// cout << "Case #" << stt << endl << ans << endl; } }
Editor is loading...