相关题连接：

一本通：

小白菜OJ：

 

 

一、DFS写法：

问题一：迷宫是否能走通？（）

 

1 #include
     
       2 #include
      
        3 using namespace std; 4 int n; 5 char a[200][200]={
   0};//用于存放迷宫数据,.为可走，#为不可走  6 int book[200][200];//用于标记该点是否被访问,0为未被访问，1为已经访问  7 int next[4][2]={
   {
   0,-1},{-1,0},{
   0,1},{
   1,0}};//存储下一步坐标累加数  8 int stx, sty, edx, edy;//分别代表迷宫初始位置、目标位置坐标  9 bool f;//标记迷宫是否能走通 10 void dfs(int x, int y)11 {12     //如果到达目标坐标，则打印输出，递归出口 13     if(x==edx&&y==edy) {14         f=true;15     }16     //尝试四方向的邻居坐标 17     for(int i=0; i<4; i++)18     {19         //计算下一个点的坐标 20         int nx=x+next[i][0];21         int ny=y+next[i][1];22  23         if(nx<0 || nx>n-1 || ny<0 || ny>n-1) continue;//判断是否越界24         if(book[nx][ny]==0 && a[nx][ny]=='.')25         {26             book[nx][ny]=1;//试探 27             dfs(nx, ny);28             //book[nx][ny]=0;//回溯 注意此处不需要回溯，否则就会超时29         } 30     } 31 }32 int main()33 {34     int k;35     scanf("%d",&k);36     while(k--)37     {38         f=false;//刚开始假定迷宫走不通39         memset(book,0,sizeof(book)); //book初始化为0 40         scanf("%d",&n);41         for(int i=0; i
      
     

 

 

 

问题二：有多少种走法？

 

问题三：输出每条走法？

 

问题四：输出最短路径数？（）

 

1 #include 
     
       2 int a[51][51],book[51][51]; 3 int next[4][2]= {
   {
   0,-1},{-1,0},{
   0,1},{
   1,0}};//这里一定要和数学上的坐标进行区分，x,y分别代表行和列 4 int n, m;//n行m列迷宫  5 int min=999999999;//用于存放最短步数,并设定min初始值为一个较大值  6 int stx,sty,edx,edy;//分别代表迷宫初始位置、目标位置坐标 7 bool f=false;//刚开始假定迷宫走不通  8 void dfs(int x,int y,int step) { 9     int nx,ny;//---->>>>注意这一行一定只能写在dfs内<<<<<----- 10     if(x==edx&&y==edy) {11         f=true;12         if(step
      
       n||ny<1||ny>m) {
   //判断是否越界21             continue;22         }23         if(book[nx][ny]==0&&a[nx][ny]==0) {24             book[nx][ny]=1;25             dfs(nx,ny,step+1);26             book[nx][ny]=0;//收回不能丢27         }28     }29 }30 int main() {31     scanf("%d%d",&n,&m);32     for(int i=1; i<=n; i++) {33         for(int j=1; j<=m; j++) {34             scanf("%d",&a[i][j]);35         }36     }37     scanf("%d%d%d%d",&stx,&sty,&edx,&edy);38     book[stx][sty]=1;//这里就和全排列有点不一样，因为这里进去之后就要发生改变，而全排列进去之后不改变39     dfs(sty,sty,0);40     if(!f)printf("No Way!");41     else printf("%d\n",min);42     return 0;43 }
      
     

 

二、BFS写法：