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 |
G++1A ,C++WA ,为什么#include<iostream> #include<string.h> #include<queue> #include<cstdio> #include<algorithm> using namespace std; int rotp[4]= {3,0,1,2}; char graph[50][50]; int step[50][50],Ans; int n,m; int dx[4]={0,-1,0,1}; int dy[4]={-1,0,1,0}; struct node { int x,y; }; node S,temp,temp_1,E; void BFS() { queue<node>Q; step[S.x][S.y]=0; Q.push(S); while(!Q.empty()) { temp=Q.front(); Q.pop(); for(int i=0;i<4;++i) { temp_1.x=temp.x+dx[i]; temp_1.y=temp.y+dy[i]; if(temp_1.x>=0&&temp_1.x<n&&temp_1.x>=0&&temp_1.y<m&&graph[temp_1.x][temp_1.y]!='#'&&(step[temp_1.x][temp_1.y]==-1||step[temp_1.x][temp_1.y]>step[temp.x][temp.y]+1)) { step[temp_1.x][temp_1.y]=step[temp.x][temp.y]+1; Q.push(temp_1); } } } } struct Ant { int x,y; int step; int dx[4]; int dy[4]; int jud() { for(int i=0; i<4; ++i) { int temp_x=x+dx[i]; int temp_y=y+dy[i]; if(temp_x>=0&&temp_x<n&&temp_y>=0&&temp_y<m&&graph[temp_x][temp_y]!='#') return i; } return -1; } void take(int ctor) { int temp_dx[4]; int temp_dy[4]; for(int i=0; i<4; ++i) { temp_dx[i]=dx[(i+ctor)%4]; temp_dy[i]=dy[(i+ctor)%4]; } for(int i=0; i<4; ++i) { dx[i]=temp_dx[i]; dy[i]=temp_dy[i]; } } }; int main() { Ant left_ant,right_ant; int T; scanf("%d",&T); while(T--) { memset(step,-1,sizeof(step)); Ans=0; scanf("%d%d",&m,&n); for(int i=0; i<n; ++i) { getchar(); for(int j=0; j<m; ++j) { scanf("%c",&graph[i][j]); } } for(int i=0; i<n; ++i) //找到S起始点 { for(int j=0; j<m; ++j) { if(graph[i][j]=='S') { left_ant.x=right_ant.x=i; left_ant.y=right_ant.y=j; left_ant.step=0; right_ant.step=0; S.x=i; S.y=j; } if(graph[i][j]=='E') { E.x=i; E.y=j; } } } left_ant.dx[0]=0,left_ant.dx[1]=-1,left_ant.dx[2]=0,left_ant.dx[3]=1; left_ant.dy[0]=-1,left_ant.dy[1]=0,left_ant.dy[2]=1,left_ant.dy[3]=0; right_ant.dx[0]=0,right_ant.dx[1]=-1,right_ant.dx[2]=0,right_ant.dx[3]=1; right_ant.dy[0]=1,right_ant.dy[1]=0,right_ant.dy[2]=-1,right_ant.dy[3]=0; do { int i=left_ant.jud(); // printf("(%d,%d)-->%d\n",left_ant.x,left_ant.y,i); if(i==-1) break; left_ant.x=left_ant.x+left_ant.dx[i]; left_ant.y=left_ant.y+left_ant.dy[i]; left_ant.take(rotp[i]); ++left_ant.step; } while(graph[left_ant.x][left_ant.y]!='E'); do { int i=right_ant.jud(); // printf("(%d,%d)-->%d\n",right_ant.x,right_ant.y,i); if(i==-1) break; right_ant.x=right_ant.x+right_ant.dx[i]; right_ant.y=right_ant.y+right_ant.dy[i]; right_ant.take(rotp[i]); ++right_ant.step; } while(graph[right_ant.x][right_ant.y]!='E'); BFS(); if(step[E.x][E.y]!=-1) Ans=step[E.x][E.y]+1; printf("%d %d %d\n",left_ant.step+1,right_ant.step+1,Ans); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator