pku 1101 bfs 可怜的大法师之简单版.txt

ACM资料大集合

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

//PKU 1101 BFS 可怜的大法师之简单版
#define PI 3.1415926
#define MH make_heap
#define OH pop_heap
#define PH push_heap
#define PB push_back
#define OB pop_back
#define NMAX 100

typedef struct ooppain
{
	bool visited;
	bool cango;
	int len;
}ooppain;

typedef struct oopqueue
{
	int x;
	int y;
}oopqueue;

ooppain pain[NMAX][NMAX];
char map[NMAX][NMAX];
int fx;
int fy;

int search(int sx,int sy,int ex,int ey)
{
	oopqueue queue[NMAX*NMAX];
	oopqueue qt,qs;
	int s,t,i,j;
	s=0,t=0;
	qt.x=sx;
	qt.y=sy;
	pain[qt.x][qt.y].len=0;
	pain[qt.x][qt.y].visited=true;
	queue[t++]=qt;
	while(s<t)
	{
		qt=queue[s++];
//		printf("qt.x=%d qt.y=%d\n",qt.x,qt.y);
		for(i=1;i<=4;i++)
		{
			if(i==1)
			{
				j=1;//注意剪枝
				while(pain[qt.x+j][qt.y].cango==true && pain[qt.x+j][qt.y].visited==false) 
				{	qs.x=qt.x+j;	qs.y=qt.y;
					pain[qs.x][qs.y].visited=true;
					pain[qs.x][qs.y].len=pain[qt.x][qt.y].len+1;
					if(qs.x==ex && qs.y==ey) return pain[qs.x][qs.y].len;
					queue[t++]=qs;
					j++;
				}
			}
			if(i==2)
			{
				j=1;
				while(pain[qt.x-j][qt.y].cango==true && pain[qt.x-j][qt.y].visited==false) 
				{	qs.x=qt.x-j;	qs.y=qt.y;
					pain[qs.x][qs.y].visited=true;
					pain[qs.x][qs.y].len=pain[qt.x][qt.y].len+1;
					if(qs.x==ex && qs.y==ey) return pain[qs.x][qs.y].len;
					queue[t++]=qs;
					j++;
				}
			}
			if(i==3)
			{
				j=1;
				while(pain[qt.x][qt.y+j].cango==true && pain[qt.x][qt.y+j].visited==false) 
				{	qs.x=qt.x;	qs.y=qt.y+j;
					pain[qs.x][qs.y].visited=true;
					pain[qs.x][qs.y].len=pain[qt.x][qt.y].len+1;
					if(qs.x==ex && qs.y==ey) return pain[qs.x][qs.y].len;
					queue[t++]=qs;
					j++;
				}
			}
			if(i==4)
			{
				j=1;
				while(pain[qt.x][qt.y-j].cango==true && pain[qt.x][qt.y-j].visited==false) 
				{	qs.x=qt.x;	qs.y=qt.y-j;
					pain[qs.x][qs.y].visited=true;
					pain[qs.x][qs.y].len=pain[qt.x][qt.y].len+1;
					if(qs.x==ex && qs.y==ey) return pain[qs.x][qs.y].len;
					queue[t++]=qs;
					j++;
				}
			}
		}
	}
	return -1;
}

void create(int l,int h)
{	//地图的设置，将周围留出一圈的空地，外面再留一圈的障碍
	int i,j;
	for(i=1;i<=l;i++)
	{
		for(j=1;j<=h;j++)
		{
			if(map[i][j]=='X') pain[i+2][j+2].cango=false;
			else pain[i+2][j+2].cango=true;
		}
		pain[i+2][2].cango=pain[i+2][h+3].cango=true;
	}
	for(j=1;j<=h;j++)
	{
		pain[2][j+2].cango=pain[l+3][j+2].cango=true;
	}
	pain[2][2].cango=pain[2][h+3].cango=pain[l+3][2].cango=pain[l+3][h+3].cango=true;
	for(i=1;i<=l+4;i++) pain[i][1].cango=pain[i][h+4].cango=false;
	for(i=1;i<=h+4;i++) pain[1][i].cango=pain[l+4][i].cango=false;
}

void print_map(int l,int h)
{
	int i,j;
	printf("l=%d h=%d\n",l,h);
	for(i=1;i<=l+4;i++)
	{
		for(j=1;j<=h+4;j++) printf("%d ",pain[i][j].cango);
		printf("\n");
	}
}

void solve(int l,int h,int sx,int sy,int ex,int ey)
{
	int i,j,ans;
	for(i=1;i<=l+4;i++)
		for(j=1;j<=h+4;j++)
			pain[i][j].visited=false;
	pain[sx][sy].cango=pain[ex][ey].cango=true;//改为可走
//	print_map(l,h);
	ans=search(sx,sy,ex,ey);
	pain[sx][sy].cango=pain[ex][ey].cango=false;//用完后，改回来
	if(ans>=0) printf(" %d segments.\n",ans);
	else printf(" impossible.\n");
}

int main()
{
	int l,h,i,j,sx,sy,ex,ey,cnum=0,dnum;
//	freopen("game.out","w",stdout);
	scanf("%d %d",&l,&h);
	while(!(l==0 && h==0))
	{
		getchar();
		for(i=1;i<=h;i++)
		{
			for(j=1;j<=l;j++)
				scanf("%c",&map[j][i]);//注意输入时坐标对调
			getchar();
		}
		create(l,h);
//		print_map(l,h);
		dnum=0;
		printf("Board #%d:\n",++cnum);
		scanf("%d %d %d %d",&sx,&sy,&ex,&ey);
		while(!(sx==0 && sy==0 && ex==0 && ey==0))
		{
//			printf("sx=%d\n",sx);
			sx+=2;sy+=2;ex+=2;ey+=2;
			printf("Pair %d:",++dnum);
			solve(l,h,sx,sy,ex,ey);
			scanf("%d %d %d %d",&sx,&sy,&ex,&ey);
		}
		printf("\n");
		scanf("%d %d",&l,&h);
	}
	return 0;
}