HDU 2612 Find a way（BFS）

深碍√TFBOYSˉ_ 2022-06-18 10:08 96阅读 0赞

提交判断的链接 [ 题目提交ＨＤＵ  
][Link 1]

HDU 或 HDOJ 2612 Find a way (两次 BFS)

[  
][Link 1]

#include <iostream> //结果正确，提交AC
    #include <cstdio>
    #include <cstring>
    #include <queue>
    using namespace std;
    #define maxn 210
    int step1[maxn][maxn];  //记录Y走的步数
    int step2[maxn][maxn];  //记录W走的步数
    int visit[maxn][maxn];  //标记走过与否
    char tu[maxn][maxn];
    struct node{    //便于向队列中插入二维坐标
    	int x,y;
    }st1,st2;
    int dx[]={1,0,-1,0};    //指定四个方向（下右上左）
    int dy[]={0,1,0,-1};
    int n,m;
    int check(int x,int y)
    {
    	if(x<n && x>=0 && y<m && y>=0 && ! visit[x][y] && tu[x][y]!='#')
    		return 0;
    	return 1;   //代表越界
    }
    void BFS(node st,int step[][210])   //BFS的模板
    {
    	queue<node>Q;   //BFS不同于DFS，BFS不用递归调用自己。while即可遍历全部
    	Q.push(st);
    	visit[st.x][st.y]=1;
    	while(!Q.empty()){
    		node t=Q.front();//固定格式，取值然后弹出
    		Q.pop();
    		for(int i=0;i<4;i++){
    			node temp;
    			temp.x = t.x + dx[i];
    			temp.y = t.y + dy[i];
    			if(check(temp.x , temp.y))//如果越界
    				continue;
    			Q.push(temp);
    			step[temp.x][temp.y]=step[t.x][t.y]+1;  //层数加一
    			visit[temp.x][temp.y]=1;
    		}
    	}
    	return ;
    }
    int main()
    {
    	while(cin>>n>>m){
    		for(int i=0;i<n;i++){
    			scanf("%s",tu[i]);
    			for(int j=0;j<m;j++){
    				if(tu[i][j]=='Y'){
    					st1.x=i;st1.y=j;
    				}
    				if(tu[i][j]=='M'){
    					st2.x=i;st2.y=j;
    				}
    			}
    		}
    		memset(visit,0,sizeof(visit));
    		memset(step1,0,sizeof(step1));
    		BFS(st1,step1);   //向step1数组中存入数据
    		memset(visit,0,sizeof(visit));
    		memset(step2,0,sizeof(step2));
    		BFS(st2,step2);   //向step2数组中存入数据
    		int ans=maxn;
    		for(int i=0;i<n;i++){
    			for(int j=0;j<m;j++){
    				int t1 = step1[i][j];
    				int t2 = step2[i][j];
    				if(tu[i][j]=='@' && t1!=0 && t2!=0){    //求解过程
    					if(t1 +t2 < ans)
    						ans=t1+t2;
    				}
    			}
    		}
    		cout<<ans*11<<endl;
    	}
    	return 0;
    }

希望有所帮助！ ![大笑][laugh.gif] ![大笑][laugh.gif] ![大笑][laugh.gif]

[  
][Link 1]

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=2612
[laugh.gif]: /images/20220618/3a678fede42f4766a3ec7affb25a1d97.png