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