#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int delta[4][2]={-1,0,0,1,1,0,0,-1};
bool map[80][80];
int dist[80][80];
int queue[2000];
int qs,qt;
int n,m;
int sx,sy,ex,ey;
bool isin(int x,int y)
{
	return x>=0&&x<=n+1&&y>=0&&y<=m+1;
}
int calc(int sx,int sy,int ex,int ey)
{
	int cx,cy,nx,ny,end;
	bool save=map[ex][ey];
	map[ex][ey]=false;
	qs=qt=0;
	memset(dist,-1,sizeof(dist));
	dist[sx][sy]=0;
	queue[qt++]=sx<<8|sy;

	while(qs<qt)
	{
		end=qt;
		for(;qs<end;qs++)
		{
			cx=queue[qs]>>8;
			cy=queue[qs]&0xff;
//			printf("<%d,%d>:%d\n",cx,cy,dist[cx][cy]);
			for(int i=0;i<4;i++)
			{
				nx=cx+delta[i][0];
				ny=cy+delta[i][1];
				for(;isin(nx,ny)&&!map[nx][ny];nx+=delta[i][0],ny+=delta[i][1])
				{
					if(dist[nx][ny]!=-1)
						continue;
					dist[nx][ny]=dist[cx][cy]+1;
					queue[qt++]=nx<<8|ny;
				}
			}
		}
		if(dist[ex][ey]!=-1) break;
	}
	map[ex][ey]=save;
	return dist[ex][ey];
}
int main()
{
	int tc=1;
	char ch;
	while(scanf("%d%d",&m,&n)!=EOF)
	{
		if(n+m==0) break;
		getchar();
		printf("Board #%d:\n",tc++);
		memset(map,false,sizeof(map));
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				ch=getchar();
				map[i][j]=(ch=='X')?true:false;
			}
			getchar();
		}
		int ans,pair=1;
		while(scanf("%d%d%d%d",&sy,&sx,&ey,&ex)!=EOF)
		{
			if(sy+sx+ey+ex==0) break;
			ans=calc(sx,sy,ex,ey);
			if(ans==-1)
			printf("Pair %d: impossible.\n",pair++);
			else 
			printf("Pair %d: %d segments.\n",pair++,ans);
		}
		printf("\n");
	}
	return 0;
}

• Re:C++ WA,G++ AC 莫非是我代码有问题? (37) cotton 2011-01-25 15:20:22
• Re:C++ WA,G++ AC 莫非是我代码有问题? (40) GardenInSkyr 2011-07-25 21:27:09