Untitled
unknown
plain_text
2 years ago
1.6 kB
7
Indexable
// In Practice, You should use the statndard input/output // in order to receive a score properly. // Do not use file input and output. Please be very careful. #define _CRT_SECURE_NO_WARNINGS #define INF 10000000 #include<iostream> using namespace std; int n,m,xstart,ystart,xtarget,ytarget; int map[51][51],visit[51][51]; int mQ[500000],f,r; int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; void push(int x){ r++; mQ[r]=x; } int pop(){ f++; return mQ[f]; } void input(){ cin>>n>>m; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>map[i][j];visit[i][j]=0; if(map[i][j]==2){ xstart=i;ystart=j; } if(map[i][j]==3){ xtarget=i;ytarget=j; } } } } void BFS(int d){ f=r=-1; push(xstart); push(ystart); visit[xstart][ystart]=1; while(f!=r){ int x=pop(); int y=pop(); for(int i=0;i<4;i++){ for(int j=1;j<=d;j++){ int xx=x+j*dx[i]; int yy=y+dy[i]; if(xx<0||xx>=n||yy<0||yy>=m||map[xx][yy]==0||visit[xx][yy]==1) continue; if(xx==xtarget&&yy==ytarget){ visit[xx][yy]=1; return; } visit[xx][yy]=1; push(xx); push(yy); } } } } void reset(){ for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ visit[i][j]=0; } } } int main(int argc, char** argv) { int test_case; int T; // freopen("input.txt", "r", stdin); cin >> T; int ans; for(test_case = 1; test_case <= T; ++test_case) { input(); for(int i=1;i<=n-1;i++){ BFS(i); if(visit[xtarget][ytarget]==1){ ans=i; break; } reset(); } cout << "Case #" << test_case << endl << ans << endl; } return 0; }
Editor is loading...