本文共 928 字，大约阅读时间需要 3 分钟。
迷宫
题意：下图给出了一个迷宫的平面图，其中标记为1 的为障碍，标记为0 的为可以通行的地方。 010000 000100 001001 110000 迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这个它的上、下、左、右四个方向之一。对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫，一共10 步。其中D、U、L、R 分别表示向下、向上、向左、向右走。对于下面这个更复杂的迷宫（30 行50 列），请找出一种通过迷宫的方式，其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。请注意在字典序中D<L<R<U。 题解：BFS,要使字典序最小，按DLRU的顺序找，第一个序列就是
#include #include using namespace std;int vis[30][50];int m[4][2]={ { 1,0},{ 0,-1},{ 0,1},{ -1,0}};char c[4]={ 'D','L','R','U'};string s[30];struct node{ int x; int y; string str;};void bfs(){ queue q; node p; p.x=0,p.y=0,p.str=""; q.push(p); vis[0][0]=1; while(q.size()){ node t=q.front(); q.pop(); if(t.x==29&&t.y==49){ cout< < =0&&p.x<30&&p.y>=0&&p.y<50&&s[p.x][p.y]=='0'){ vis[p.x][p.y]=1; p.str=t.str+c[i]; q.push(p); } } }}int main(){ for(int i=0;i<30;i++){ cin>>s[i]; } bfs(); return 0;}
转载地址：http://xpnki.baihongyu.com/