【HDU 2612】Find a way（bfs）

題目連結：http://acm.hdu.edu.cn/showproblem.php?pid=2612

題意：

yifenfei要回甯波見他的好朋友Merceki，但是yifenfei住在鄉村，而Merceki住在市中心，是以他們約定在KFC處碰面，但是在甯波有很多KFC，他們想選擇一個使他們到達KFC總時間最少的一個KFC，現在給你一個地圖，求出最小總時間，倆人每走一步都要花費11分鐘，地圖中'Y'代表yifenfei的起始點，'M'代表Merceki的起始點，'@'代表KFC，'#'代表走不通的路，'.'代表能走的路。

思路：

本來想着就以Y為起點，M為終點，利用bfs算出起點到終點（中途必須經過一個KFC）的最少時間，結果發現記憶體超限，可能因為沒有标記走過的地方導緻隊列裡的記憶體過大吧，無奈 ~ 隻能換種方法了

利用bfs分别求出倆人到每個KFC的距離，篩選出花費時間最少的。為了減少一些時間複雜度，每次都周遊整個地圖是，這樣就可以記錄下到所有KFC的最小距離。

My  Code：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<math.h>
#include<set>
using namespace std;
#define INF 1e9
typedef long long ll;
char ch[300][300];
int vis[300][300],n,m;
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
struct point
{
	int x,y,step;
}start1,start2;
int node[205][205],dis[3][40005];
///node用來标記KFC的位置，dis用來記錄Y到所有KFC、M到所有KFC的距離 
void bfs(int t)
{
	point start;
	if(t == 1) start = start1;///1代表Y 
	else start = start2;///2代表M 
	memset(vis,0,sizeof(vis));
	start.step = 0;
	vis[start.x][start.y] = 1;
	point cur,nxt;
	queue<point> q;
	q.push(start);
	while(!q.empty())
	{
		cur = q.front();
		q.pop();
		for(int i = 0; i < 4; i++)
		{
			nxt.x = cur.x+dir[i][0];
			nxt.y = cur.y+dir[i][1];
			nxt.step = cur.step + 1;
			if(nxt.x>=0 && nxt.x<n && nxt.y>=0 && nxt.y<m && vis[nxt.x][nxt.y] == 0 && ch[nxt.x][nxt.y] != '#')
			{
				vis[nxt.x][nxt.y] = 1;
				///碰到一個KFC，記錄下到它的距離 
				if(ch[nxt.x][nxt.y] == '@') dis[t][node[nxt.x][nxt.y]] = nxt.step;
				q.push(nxt);
			}
		}
	}
}
int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		int cunt = 1;
		for(int i = 0; i < n; i++)
		{
			getchar();
			scanf("%s",ch[i]);
			for(int j = 0; j < m; j++)
			{
				if(ch[i][j] == 'Y')
				{
					start1.x = i;
					start1.y = j;
				}
				if(ch[i][j] == 'M')
				{
					start2.x = i;
					start2.y = j;
				}
				if(ch[i][j] == '@')
				{
					node[i][j] = cunt;
					cunt++;
				}
			}
		}
		bfs(1);///Y到各個KFC的距離 
		bfs(2);///M到各個KFC的距離
		int minn = INF;
		///找出一個兩人花費總時間最少的KFC 
		for(int i = 1; i < cunt; i++)
		{
			minn =  min(minn,dis[1][i]+dis[2][i]);
		}
		printf("%d\n",minn*11);
	}
    return 0;
}