ACM-bfs之Find a way——hdu2612

66

这道题就是队列加BFS，我用的方法就是两个人都搜索一遍，

KFC数组初始化为-1，第一个人走到任何一个KFC，将步数加过去，

第二个人走到相应的也把步数加过去，

这样最后找最小的就可以了。

为什么用-1呢，因为如果输入下图：

//Find a way


#include <iostream>
#include <string.h>
#include <queue>
using namespace std;

int map[1001][1001];
bool vis[1001][1001];
int KFC[50001];
int dis[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int m,n,num;

// 坐标结构体
struct Coordinate
{
	int x,y,step;
};

// 判断是否界外或者撞墙或者已经走过
bool isforbid(int x,int y)
{
	if(x<0 || y<0 || x>=m || y>=n)	return 1;
	if(map[x][y]==-1 || vis[x][y]==1)	return 1;
	return 0;
}

void bfs(int x,int y)
{
	// 初始化
	memset(vis,0,sizeof(vis));
	queue <Coordinate> q;	
	Coordinate ft,next;
	int i;

	// 先压入一个值，避免空队列
	ft.x=x,ft.y=y,ft.step=0;
	vis[x][y]=1;
	q.push(ft);
	
	while(!q.empty())
	{

		ft=q.front();
		q.pop();

		// 如果搜索到任何一个KFC，都记录下来，并继续执行
		if(map[ft.x][ft.y]>0)	KFC[map[ft.x][ft.y]]+=ft.step;
		
		for(i=0;i<4;++i)
		{
			next.x=ft.x+dis[i][0];
			next.y=ft.y+dis[i][1];
			if(isforbid(next.x,next.y))	continue;

			next.step=ft.step+1;
			vis[next.x][next.y]=1;
			q.push(next);
		}
	}
}


int main()
{
	char c;
	int i,j,min;
	int yx,yy,mx,my;
	while(cin>>m>>n)
	{
		memset(KFC,-1,sizeof(KFC));
		num=1;

		// 输入时寻找Y点，M点坐标，并且将每一个KFC用1,2,3,4等字符代替
		for(i=0;i<m;++i)
			for(j=0;j<n;++j)
			{
				cin>>c;
				if(c==‘Y‘)	{yx=i;yy=j;map[i][j]=0;}
				else if(c==‘M‘)	{mx=i;my=j;map[i][j]=0;}
				else if(c==‘@‘)	map[i][j]=num++;
				else if(c==‘#‘)	map[i][j]=-1;
				else	map[i][j]=0;
			}
		

		bfs(yx,yy);
		bfs(mx,my);
		
		
		
		
		// 遍历每个KFC中两人到达距离和，找最小
		min=999999999;
		for(i=1;i<num;++i)
		{
			if(KFC[i]==-1)	continue;
			min=(min>KFC[i]+1)?KFC[i]+1:min;
		}
		cout<<min*11<<endl;

	}
	return 0;
}

ACM-bfs之Find a way——hdu2612,布布扣,bubuko.com

ACM-bfs之Find a way——hdu2612

原文：http://blog.csdn.net/lttree/article/details/20380143