HDU 2612 Find a way(bfs)

蔚落 2022-08-14 04:56 18阅读 0赞

题目网址：http://acm.hdu.edu.cn/showproblem.php?pid=2612

题意：Y和M想在某家KCF见面，求他们到某家KCF的时间花费最少为多少。

“\#”为墙，“@”为KFC，“.“为路，每步花费1时间。

思路：分别以Y，M为起点进行两次bfs，得出他们到每一家KFC的时间，分别用两个数组统计time1、time2，最后通过for循环比较出time1+time2的最小值。注意走过的路要进行标记，还要注意初始化，注意越界。由于有多家KFC，所以当搜到“@”时还要再继续搜下去，不要忘记标记它和把它扔到队列里。

code：

#include<stdio.h>
    #include<string.h>
    #include<iostream>
    #include<string>
    #include<queue>
    #define INF 0x3f3f3f 
    using namespace std;
    int n,m,x1,y1,x2,y2;
    int dx[]={0,0,1,-1};
    int dy[]={1,-1,0,0};
    int vis[200][200],flag;
    int time1[200][200];
    int time2[200][200];
    string map[200];
    struct node
    {
    	int x,y,step;
    }ll,t;
    void bfs(int x,int y)
    {
    	queue<node> q;
    	ll.x=x;
    	ll.y=y;
    	ll.step=0;
    	q.push(ll);
    	while(!q.empty())
    	{
    		t=q.front();
    		q.pop();
    		for(int i=0;i<4;i++)
    		{
    			int a=t.x+dx[i];
    			int b=t.y+dy[i];
    			int s=t.step;
    			if(a<0||a>n||b<0||b>m||vis[a][b]||map[a][b]=='#')
    				continue;
    			else if(map[a][b]=='@')
    			{
    				if(flag==1)
    				{
    					if(s+1<time1[a][b])
    						time1[a][b]=s+1;
    				}
    				else if(flag==2)
    				{
    					if(s+1<time2[a][b])
    						time2[a][b]=s+1;	
    				}
    			}
    			vis[a][b]=1;
    			ll.x=a;
    			ll.y=b;
    			ll.step=s+1;
    			q.push(ll);
    		}
    	}
    }
    int main()
    {
    	while(cin>>n>>m)
    	{
    		for(int i=0;i<n;i++)
    			cin>>map[i];
    		for(int i=0;i<n;i++)
    			for(int j=0;j<m;j++)
    			{
    				if(map[i][j]=='Y')
    				{
    					x1=i;
    					y1=j;
    				}
    				else if(map[i][j]=='M')
    				{
    					x2=i;
    					y2=j;
    				}
    			}
    		memset(vis,0,sizeof(vis));
    		memset(time1,INF,sizeof(time1));
    		flag=1;
    		bfs(x1,y1);
    		memset(vis,0,sizeof(vis));
    		memset(time2,INF,sizeof(time2));
    		flag=2;
    		bfs(x2,y2);
    		int minn=INF;
    		for(int i=0;i<n;i++)
    		    for(int j=0;j<m;j++)
    		    {
        			if(time1[i][j]!=INF&&time2[i][j]!=INF)
    		            minn=min(time1[i][j]+time2[i][j],minn);
        		} 
          	cout<<minn*11<<endl;
    	}
    	return 0;
    }

提交的时候交C++显示编译错误，交G++ AC。