笨笨熊交通篇--广度搜索

我不是女神ヾ 2022-08-27 04:46 240阅读 0赞

题目如上篇博客，上篇博客的评论有人说用bfs好像没AC，我也尝试了写了写，看了下评论的那个人的代码，感觉思想没错误哈，看华为的官方微博上评论说在输入输出上可能有问题，我也贴一下自己写的代码哈

#include <iostream>
    #include <queue>
    using std::endl;
    using std::cin;
    using std::cout;
    using std::queue;
    //定义图map中每个点的坐标
    struct node{
    	int x;
    	int y;
    };
    //定义广度搜索的四个方向
    int direction[4][2]={-1,0,0,-1,1,0,0,1};
    //输入的行和列
    int R,C;
    //定义最后是否能到达终点的标记
    bool flag;
    //图的二维矩阵,里面字符a表示已经被访问过(此处就省去了标记数组)
    char map[100][100];
    void bfs(int i,int j)
    {
    	queue<node> nodequeuue;
    	//将开始点B压入队列中
    	node startpoint;
    	startpoint.x=i;
    	startpoint.y=j;
    	nodequeuue.push(startpoint);
    	//标记B已经走过
    	map[i][j]='a';
    	//当队列不为空的时候
    	while(!nodequeuue.empty())
    	{
    		node temp;
    		temp=nodequeuue.front();
    		nodequeuue.pop();
    		for(int s=0;s<4;++s)
    		{
    			//先向下、左、上、右的方向搜索
    			//必须用坐标(x,y)来保存坐标
    			int x=temp.x+direction[s][0];
    			int y=temp.y+direction[s][1];
    			//判断是否到达了终点
    			if(x>=0&&x<R&&y>=0&&y<C)
    			{//当在图map的范围内
    				if(map[x][y]!='a'&&map[x][y]!='#')
    				{
    					if(map[x][y]=='H')
    					{
    						flag=true;
    						return;
    					}
    					//标记走过的点为字符a
    					map[x][y]='a';
    					//压入队列
    					node point;
    					point.x=x;
    					point.y=y;
    					nodequeuue.push(point);
    				}
    			}
    		}
    	}
    }
    int main()
    {
    	int sx,sy;
    	while(cin >> R >> C)
    	{
    		flag=false;
    		for(int i=0;i<R;++i)
    			for(int j=0;j<C;++j)
    			{
    				cin >> map[i][j];
    				//记录B位置
    				if(map[i][j]=='B')
    				{
    					sx=i,
    					sy=j;
    				}
    			}
    		bfs(sx,sy);
    		if(flag)
    			cout << "Y" << endl;
    		else
    			cout << "N" << endl;
    	}
    	return 0;
    }