| ||||||||||
| 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