小单刷题笔记之迷宫（bfs）
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
下图给出了一个迷宫的平面图，其中标记为 1的为障碍，标记为 0的为可以通行的地方。
010000000100001001110000迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。
对于上面的迷宫，从入口开始，可以按 DRRURRDDDR 的顺序通过迷宫， 一共 10步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。 对于下面这个更复杂的迷宫（30 行 50列），请找出一种通过迷宫的方式，其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。
请注意在字典序中 D<L<R<U
010101010010110010010101100101101001000010001010100000100010000010101001000010000000100110011010010101111011010010001000001101001011100011000000010000010000000010101000110100001010000010101010110010110001111100000010100001001010001010000010110000000011001000110101000010101100011010011010101011110111000110110101010010010010100000010001010011100000001010000010100010011010101011111001100001000011101000111000001010100001100010000001000101001100001001110001101000011100100010010101010101010100011010000001000010010000010100101010111010001010101000010111100100101001001000010000010101010100100100010100000000100000001010110011110100011000001010101000111010101001110000100001100001011001111011010000100010101010100001101010100101000010100000111011101001100000001011000100001011001011010010111000000001001010100100000001010010000100010000010001111010100100101001010101101001010100011010101101110000110101110010100001000011000000101001010000010001110000100000100011000011010110100000010010100100100001110110100101000101000000001110110010110101101010100001001010000100001101010100001000100010010001000101011010000100011001000100001010100101010101111101001000000100101000000110010100101001000001000000000010110100000010011101110010010000111010010110111010000000011010001000100010000000100001110100000011001110101000101000100010001111100010101001010000001000100000101001010010101100000001001010100010111010000011110000100001000000011011100000000100000000101110000001100111010111010001000110111010101101111000思路：
迷宫问题应该bfs中较为经典的题目了，这道题博主之前做过一道类似的。
参考：迷宫问题（手写queue）
这次做有新的体会，从别人的题解发现了新的小技巧，记录下来。首先这道题的数据输入要处理一下，我第一遍敲代码的时候就失误了，这个输入数据不能用int型来读入，中间没有空格。所以我们开一个string数组来保存。
string map_[33];之后我们写一层循环就可以读入数据了。之后就是考虑bfs要怎么写，代码如下
const char d[4]={'D','L','R','U'};const int dr[4]={1,0,0,-1};const int dc[4]={0,-1,1,0};string map_[33];struct step{int x,y;string s;step(int xx,int yy,string ss):x(xx),y(yy),s(ss){}};queue q;void bfs(){step u(0,0,"");map_[0][0]='1';q.push(u);while(!q.empty()){step a=q.front();if(a.x==29&&a.y==49){cout<<a.s;break;}for(int i=0;i<4;i++){int newx=a.x+dr[i],newy=a.y+dc[i];if(newx=30||newy=50||map_[newx][newy]=='1')continue;map_[newx][newy]='1';step v(newx,newy,a.s+d[i]);q.push(v);}q.pop();}bfs较之dfs，通俗点说，我觉得bfs就像一颗石头扔进水里荡起的涟漪，一层一层的向外扩散。而dfs则是深度优先遍历每条路径。我们先定义一个结构体，里面有当前的横纵坐标X,Y和我们最后要输出的步骤string s。搞一个队列 q，先把队首的元素加进去，横纵坐标皆为0，s为空串。接下来开始进入循环，循环条件是队列不为空。边界值先设置一下，如果走到终点了，就输出步骤。并且跳出循环。接下来这层for循环可以省去冗杂的代码，看一下代码开头定义的那三个数组。
const char d[4]={'D','L','R','U'};const int dr[4]={1,0,0,-1};const int dc[4]={0,-1,1,0};for(int i=0;i<4;i++){int newx=a.x+dr[i],newy=a.y+dc[i];if(newx=30||newy=50||map_[newx][newy]=='1')continue;map_[newx][newy]='1';step v(newx,newy,a.s+d[i]);q.push(v);}下标从0到3，分别对应着，向下走、向左走、向右走、向上走。顺序要注意一下，因为他要求输出字典序较小的那个对不对，所以我们走的方向也一定按照字典序排。按照bfs算法，最后一个队首满足条件的应该是最短路径，我们把走的顺序按字典序提前排列好，那么第一个到达终点的路径就是答案。如果x，y越界了就continue，map是1,也不能走。把走过的地方标记成1，如果后续有从别的路径到这里来的，就不要再走了，一定没有前面的方式更优。把满足条件的push进队列，最后把队首元素删除。（注意一下这个continue条件）顺序比较重要，如果写成if(newx>=0&&newx=0&&newy<=50&&map_[newx][newy]=='1')
这样的话可能会导致数组越界。
回顾一下bfs,拿这道题来说，队首的每个元素有四种可能需要尝试的路径，把这四者中满足条件的插入队列，就可以想象成把一个连通图的父节点的所有下一层子节点都放入了队列中，一次又一次直到终点。下一层的子节点都放进队列了，队首的父节点就可以弹出了，继续看下一个元素的子节点。弹到最后，一定会把到第一个到终点的那个元素变成队首，因为是有顺序的嘛，我们又按照字典序定义步骤了，所以最后队首那个元素如果满足条件，就是答案了。
