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