710

This is quite an easy problem. But it took me long time to realize that to determine the number of total game segments is nothing but counting the direction changes to reach the destination.

#include <iostream>
#include <cstdio>
#include <climits>
#include <queue>
#include <cstring>
#include <string>

using namespace std;

int w,h;
int SEGMENT;
int gr[80][80];
int visit[80][80];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

int bfs(int stx,int sty,int edx,int edy)
{
	int x,y,stp;
	int direction=0,tmpDirection;
	int tmpx,tmpy;
	queue<int> q;
	memset(visit,0,sizeof(visit));
	int step=0;
	q.push(stx);
	q.push(sty);
	q.push(step);
	q.push(direction);

	while(!q.empty())
	{
		x = q.front();q.pop();
		y = q.front();q.pop();
		stp = q.front();q.pop();
		direction = q.front();q.pop();
		visit[x][y]=1;

		for(int i=0;i<4;i++)
		{
			if(x+dx[i]==edx && y+dy[i]==edy)
			{
				if(dx[i]==0)
					tmpDirection=1;//horizontal direction
				else if(dy[i]==0)
					tmpDirection=2;//vertical direction
				if(tmpDirection!=direction)
					return stp+1;
				return stp;
			}
			if(x+dx[i]>=0 && x+dx[i]<=(h+1) && y+dy[i]>=0 && y+dy[i]<=(w+1) && visit[x+dx[i]][y+dy[i]]==0 && gr[x+dx[i]][y+dy[i]]==0)
			{
				tmpx = x+dx[i];
				tmpy = y+dy[i];
				q.push(x+dx[i]);
				q.push(y+dy[i]);
				if(dx[i]==0)
					tmpDirection=1;//horizontal direction
				else if(dy[i]==0)
					tmpDirection=2;//vertical direction
				if(tmpDirection!=direction)
					q.push(stp+1);
				else if(tmpDirection==direction)
					q.push(stp);
				q.push(tmpDirection);
			}
		}
	}
	return -1;
}


int main()
{
	char ch;
	int kase=1;
	string str;
	vector<int> path;
	int x1,x2,y1,y2;
	while(scanf("%d%c%d%c",&w,&ch,&h,&ch),w,h)
	{
		memset(gr,0,sizeof(gr));
		for(int i=1;i<=h;i++)
		{
			getline(cin,str);
			for(int j=0;j<w;j++)
			{
				if(str[j]=='X')
				gr[i][j+1]=1;
				else if(str[j]==' ')
				gr[i][j+1]=0;
			}
		}
		bool flag=0;
		int ccase=1;
		int res;
		while(scanf("%d%c%d%c%d%c%d%c",&x1,&ch,&y1,&ch,&x2,&ch,&y2,&ch))
		{
			if(x1+y1+x2+y2==0)
			break;
			res = bfs(y1,x1,y2,x2);
			if(flag==0)
				printf("Board #%d:\n",kase++);
			flag = 1;
			if(res==-1)
			printf("Pair %d: impossible.\n",ccase++);
			else
			printf("Pair %d: %d segments.\n",ccase++,res);
		}
		printf("\n");
	}
	return 0;
}