| ||||||||||
| 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 | |||||||||
求大牛帮忙,此代码runtime error#include<iostream>
using namespace std;
int row,col;
const int N=1000;
char matrix[N][N];
bool visit[N][N],h[N][N],v[N][N];
int tx,ty,sx[5],sy[5],f;
int move[4][2]={{0,-2},{0,1},{1,0},{-2,0}};
typedef struct Point{
int x,y;
char dir;
int step;
}point;
point queue[80000];
bool check(int x,int y)
{
if(x>=1 && x<=row && y>=1 && y<=col)
return true;
return false;
}
int bfs()
{
int front=0,rear=0,i;
queue[rear].step=0;
if(f==1)
{
queue[rear].x=sx[0];
queue[rear].y=sy[0];
queue[rear].dir='s';
visit[sx[0]][sy[0]]=true;
}
if(f==2){
if(sx[0]==sx[1])
{
queue[rear].dir='h';
queue[rear].x=sx[0];
if(sy[0]>sy[1])
queue[rear].y=sy[1];
else
queue[rear].y=sy[0];
h[queue[rear].x][queue[rear].y]=true;
}
else{
queue[rear].dir='v';
queue[rear].y=sy[0];
if(sx[0]>sx[1])
queue[rear].x=sx[1];
else
queue[rear].x=sx[0];
v[queue[rear].x][queue[rear].y]=true;
}
}
rear++;
point p,temp;
while(front<=rear)
{
p=queue[front++];
if(p.dir=='s' && p.x==tx && p.y==ty)
{
return p.step;
}
if(p.dir=='s')
{
for(i=0;i<4;i++)
{
temp.x=p.x+move[i][0];
temp.y=p.y+move[i][1];
if((i<2 && check(temp.x,temp.y) && check(temp.x,temp.y+1) && !h[temp.x][temp.y] && matrix[temp.x][temp.y]!='#' && matrix[temp.x][temp.y+1]!='#') ||
(i>=2 && check(temp.x+1,temp.y) && check(temp.x,temp.y) && !v[temp.x][temp.y] && matrix[temp.x+1][temp.y]!='#' && matrix[temp.x][temp.y]!='#'))
{
if(i<2)
{
temp.dir='h';
h[temp.x][temp.y]=true;
}
else {
temp.dir='v';
v[temp.x][temp.y]=true;
}
temp.step=p.step+1;
queue[rear++]=temp;
//printf("%d %d %c %d\n",temp.x,temp.y,temp.dir,temp.step);
}
}
}
else if(p.dir=='h')
{
if(check(p.x-1,p.y) && check(p.x-1,p.y+1) )
{
if( !h[p.x-1][p.y] && matrix[p.x-1][p.y]!='#' && matrix[p.x-1][p.y+1]!='#')
{
temp.x=p.x-1;
temp.y=p.y;
temp.dir='h';
temp.step=p.step+1;
h[temp.x][temp.y]=true;
queue[rear++]=temp;
}
}
if(check(p.x+1,p.y) && check(p.x+1,p.y+1))
{
if( !h[p.x+1][p.y] && matrix[p.x+1][p.y]!='#' && matrix[p.x+1][p.y+1]!='#' )
{
temp.x=p.x+1;
temp.y=p.y;
temp.dir='h';
temp.step=p.step+1;
h[temp.x][temp.y]=true;
queue[rear++]=temp;
}
}
if(check(p.x,p.y-1)){
if( !visit[p.x][p.y-1] && matrix[p.x][p.y-1]!='#' && matrix[p.x][p.y-1]!='E' )
{
temp.x=p.x;
temp.y=p.y-1;
temp.dir='s';
temp.step=p.step+1;
visit[temp.x][temp.y]=true;
queue[rear++]=temp;
}}
if(check(p.x,p.y+2)){
if( !visit[p.x][p.y+2] && matrix[p.x][p.y+2]!='#' && matrix[p.x][p.y+2]!='E' )
{
temp.x=p.x;
temp.y=p.y+2;
temp.dir='s';
temp.step=p.step+1;
visit[temp.x][temp.y]=true;
queue[rear++]=temp;
}}
}
else{
if(check(p.x+1,p.y-1) && check(p.x,p.y-1) ){
if(!v[p.x][p.y-1] && matrix[p.x][p.y-1]!='#' && matrix[p.x+1][p.y-1]!='#')
{
temp.x=p.x;
temp.y=p.y-1;
temp.dir='v';
temp.step=p.step+1;
v[temp.x][temp.y]=true;
queue[rear++]=temp;
}}
if(check(p.x,p.y+1) && check(p.x+1,p.y+1) ){
if( !v[p.x][p.y+1] && matrix[p.x][p.y+1]!='#' && matrix[p.x+1][p.y+1]!='#' )
{
temp.x=p.x;
temp.y=p.y+1;
temp.dir='v';
temp.step=p.step+1;
v[temp.x][temp.y]=true;
queue[rear++]=temp;
}}
if(check(p.x-1,p.y) ){
if( !visit[p.x-1][p.y] && matrix[p.x-1][p.y]!='#' && matrix[p.x-1][p.y]!='E')
{
temp.x=p.x-1;
temp.y=p.y;
temp.dir='s';
temp.step=p.step+1;
visit[temp.x][temp.y]=true;
queue[rear++]=temp;
}}
if(check(p.x+2,p.y) ){
if( !visit[p.x+2][p.y] && matrix[p.x+2][p.y]!='#' && matrix[p.x+2][p.y]!='E' )
{
temp.x=p.x+2;
temp.y=p.y;
temp.dir='s';
temp.step=p.step+1;
visit[temp.x][temp.y]=true;
queue[rear++]=temp;
}}
}
}
return -1;
}
int main()
{
while(scanf("%d%d",&row,&col)!=EOF)
{
if(!row && !col)
break;
memset(h,false,sizeof(h));
memset(v,false,sizeof(v));
memset(visit,false,sizeof(visit));
int i,j;
f=0;
for(i=1;i<=row;i++)
scanf("%s",matrix[i]+1);
for(i=1;i<=row;i++)
{
for(j=1;j<=col;j++)
{
//scanf("%c",&matrix[i][j]);
if(matrix[i][j]=='O')
{
tx=i;
ty=j;
}
if(matrix[i][j]=='X')
{
sx[f]=i;
sy[f++]=j;
}
}
}
//printf("%d %d\n",sx[0],sy[0]);
/*for(i=1;i<=row;i++)
{
for(j=1;j<=col;j++)
printf("%c",matrix[i][j]);
printf("\n");
}*/
int ans=0;
ans=bfs();
if(ans==-1)
printf("Impossible\n");
else
printf("%d\n",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