【HDU 2612】Find a way（bfs）

àì夳堔傛蜴生んèń 2022-04-24 13:50 113阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=2612][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;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_2612]: http://acm.hdu.edu.cn/showproblem.php?pid=2612