Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
50行代码0ms AC。。#include<cstdio> using namespace std; const int d[4][2]={{-1,0},{0,1},{1,0},{0,-1}},t[]={1,0,-1,2}; int T,n,m,sx,sy;char mp[45][45];bool vis[45][45]; struct ff{ int x,y,s; }que[1605]; bool check(int x,int y){return (1<=x&&x<=n&&1<=y&&y<=m&&mp[x][y]!='#');} int DFS(int x,int y,int flg,int s,int p){ if(mp[x][y]=='E') return s; int f,x_,y_; for(int i=0;i<4;i++){ f=(flg+t[i]*p+4)%4;x_=x+d[f][0],y_=y+d[f][1]; if(check(x_,y_)) return DFS(x_,y_,f,s+1,p); } } int BFS(){ int hed=0,tal=1,x_,y_;vis[sx][sy]=1,que[1].x=sx,que[1].y=sy,que[1].s=1; while(hed!=tal){ ++hed; for(int i=0;i<4;i++){ x_=que[hed].x+d[i][0],y_=que[hed].y+d[i][1]; if(check(x_,y_)&&!vis[x_][y_]){ vis[x_][y_]=1,que[++tal].s=que[hed].s+1,que[tal].x=x_,que[tal].y=y_; if(mp[x_][y_]=='E') return que[tal].s; } } } } int main(){ scanf("%d",&T); while(T--){ scanf("%d%d%*c",&m,&n); for(int i=1;i<=n;i++,getchar()) for(int j=1;j<=m;j++){ mp[i][j]=getchar(),vis[i][j]=0; if(mp[i][j]=='S') sx=i,sy=j; } printf("%d %d %d\n",DFS(sx,sy,0,1,-1),DFS(sx,sy,0,1,1),BFS()); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator