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

求大牛帮忙,此代码runtime error

Posted by 20091004037 at 2011-03-02 15:57:32 on Problem 3322
#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:
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