Source Code

Problem: 1101  User: yzhw 
Memory: 428K  Time: 47MS 
Language: G++  Result: Accepted 

Source Code 
# include <iostream>
# include <list>
using namespace std;
struct point
{
	int x;
	int y;
	int level;
};


int w,h;
bool map[80][80];
list<point> refer;

int bfs(int x1,int y1,int x2,int y2)
{
	refer.clear();
	point start;
	start.level=0;
	start.x=x1;
	start.y=y1;
	refer.push_back(start);
	bool used[80][80];
	memset(used,false,sizeof(used));
	while(refer.size()!=0)
	{
		point temp=refer.front();
		refer.pop_front();
		int i;
		for(i=temp.x+1;i<=w+1&&!map[i][temp.y];i++)
		{
			point temp1;
			temp1.level=temp.level+1;
			temp1.x=i;
			temp1.y=temp.y;
			if(used[temp1.x][temp1.y]) continue;
			refer.push_back(temp1);
			used[temp1.x][temp1.y]=true;
		}
		if(i<=w+1&&i==x2&&temp.y==y2) return temp.level+1;
		for(i=temp.x-1;i>=0&&!map[i][temp.y];i--)
		{
			point temp1;
			temp1.level=temp.level+1;
			temp1.x=i;
			temp1.y=temp.y;
			if(used[temp1.x][temp1.y]) continue;
			refer.push_back(temp1);
			used[temp1.x][temp1.y]=true;
		}
		if(i>=0&&i==x2&&temp.y==y2) return temp.level+1;
		for(i=temp.y+1;i<=h+1&&!map[temp.x][i];i++)
		{
			point temp1;
			temp1.level=temp.level+1;
			temp1.y=i;
			temp1.x=temp.x;
			if(used[temp1.x][temp1.y]) continue;
			refer.push_back(temp1);
			used[temp1.x][temp1.y]=true;
		}
		if(i<=h+1&&i==y2&&temp.x==x2) return temp.level+1;
		for(i=temp.y-1;i>=0&&!map[temp.x][i];i--)
		{
			point temp1;
			temp1.level=temp.level+1;
			temp1.y=i;
			temp1.x=temp.x;
			if(used[temp1.x][temp1.y]) continue;
			refer.push_back(temp1);
			used[temp1.x][temp1.y]=true;
		}
		if(i>=0&&i==y2&&temp.x==x2) return temp.level+1;
	}
	return 0;
}
int main()
{
	int count =1;
	while(1)
	{
		scanf("%d %d",&w,&h);
		memset(map,0,sizeof(map));
		if(!w&&!h) break;
		printf("Board #%d:\n",count++);
		for(int i=1;i<=h;i++)
		{
			getchar();
			for(int j=1;j<=w;j++)
			{
				char temp;
				scanf("%c",&temp);
				if(temp=='X') map[j][i]=1;
			}
		}
		int count1=1;
		while(1)
		{
			int x1,x2,y1,y2;
			scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
			if(!x1&&!x2&&!y1&&!y2) break;
			int res;
			if(res=bfs(x1,y1,x2,y2)) printf("Pair %d: %d segments.\n",count1++,res);
			else printf("Pair %d: impossible.\n",count1++);
		}
		printf("\n");
		
	}
	return 0;
}