Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

50行代码0ms AC。。

Posted by ff_666 at 2018-02-19 07:35:44 on Problem 3083
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator