DFS+回溯 求解 密室逃脱(蓝桥杯,迷宫问题)级详细

问题:

真人版密室逃脱游戏风靡全球，不仅在麻瓜世界广受欢迎，而且在魔法世界也十分流行。考虑到魔法世界的人们会使用能够瞬间移动的魔法，密室逃脱游戏在被引进魔法世界时作了一些修改：“密室迷宫”由排成n行m列的nm间房间组成，每间房间会被标记为“危险的”或者“安全的”，参加者在左上角的房间中开始游戏，通过使用红绿蓝三种不同的魔法在房间迷阵中移动（只能移动到“安全的”房间，不能移动到“危险的”房间），最后到达右下角的房间即获得胜利。三种不同魔法的效果如下：
　　“红魔法”（r）：瞬间移动到所在房间右边的第二间房；
　　“绿魔法”（g）：瞬间移动到所在房间右下方的房间；
　　“蓝魔法”（b）：瞬间移动到所在房间下方的第三间房；
　　魔法师小L最近也迷上了这款游戏，他在游戏开始前拿到了房间地图（“安全的”房间用1标记，“危险的”房间用0标记），并被告知只能使用a次红魔法，b次绿魔法和c次蓝魔法（数据保证n=1 b 3*c；m=1 b 2*a），那么请聪明的你告诉小L，他能不能胜利？如果可以，该怎么使用魔法才能安全的到达右下角的房间？

输入格式

　　输入第一行为五个整数n、m、a、b、c，用空格隔开；
　　第二行到第n 1行每行m个整数（0或1），表示房间地图（数据保证地图左上角和右下角的整数为1）

输出格式

　　若小L不能够到达终点，则输出-1；
　　若小L能够到达终点，则输出字典序最大的使用的魔法序列（用r、g、b表示，不用空格空行）。

样例输入

12 9 3 2 3
1 1 1 1 1 0 0 1 1
0 1 1 0 0 1 1 1 1
1 1 1 1 1 0 0 0 1
1 0 1 1 0 1 1 0 1
1 1 1 1 1 0 1 1 0
1 1 1 1 1 1 0 1 1
0 1 1 0 0 1 1 1 0
0 0 0 0 1 0 1 1 1
0 1 1 1 1 1 1 1 1
1 1 0 0 1 1 0 1 1
1 1 1 1 1 1 0 1 0
0 1 1 1 1 1 0 1 1

样例输出

rrgrgbbb

数据规模和约定

　　1≤n，m≤1000

代码:

1.  
   #include<stdio.h>
2.  
   #define max 1010 //定义数据最大限度//
3.  
   typedef struct node
4.  
   {
5.  
   int value; //迷宫的单元//
6.  
   int Flag; //记录该点是否走过//
7.  
   } Node;
8.  
   int n,m,flag=0,path=0; //n是长，m是宽，flag判断是否走过了终点，path记录走过的步数//
9.  
   Node a[max][max]; //定义迷宫数组//
10.  
    char b[max]; //记录走的路程//
11.  
    int tx[3]= {0,1,3}; //移动的坐标//
12.  
    int ty[3]= {2,1,0};
13.  
    char str[3]= {'r','g','b'}; //题目要求的三个方向和tx与ty对应//
14.  
    int x[3]; //三个方向最大移动的次数//
15.  
    int dfs(int i,int j)
16.  
    {
17.  
    if(i==n&&j==m) //先判断是不是到了终点//
18.  
    {
19.  
    flag=1;
20.  
    return true;
21.  
    }
22.  
    if(x[0]<0||x[1]<0||x[2]<0) //判断是否超了最大移动次数//
23.  
    {
24.  
    return false;
25.  
    }
26.  
    if(i>n||j>m) //是否越界，也算是剪枝的一种//
27.  
    {
28.  
    return false;
29.  
    }
30.  
    if(a[i][j].Flag==1) //判断该点是否走过//
31.  
    {
32.  
    return false;
33.  
    }
34.  
    a[i][j].Flag=1; //一旦进来并且没有访问过，那就将该点标记为访问//
35.  
    int Tx,Ty,l; //Tx为横移，Ty为竖移//
36.  
    path ; //path记录步数//
37.  
    for(l=0; l<=2; l )
38.  
    {
39.  
    Tx=i tx[l];
40.  
    Ty=j ty[l];
41.  
    if(a[Tx][Ty].value==1&&a[Tx][Ty].Flag==0) //判断下一步是否可以移动//
42.  
    {
43.  
    b[path]=str[l]; //进来代表可以，所以把该步赋值给b//
44.  
    x[l]--; //然后将这步减一//
45.  
    if(dfs(Tx,Ty)==true) //如果该点可以走完那就返回true//
46.  
    {
47.  
    return true;
48.  
    }
49.  
    x[l] ; //如果该点行不通返回赋的其他所有值，并且返回false//
50.  
    }
51.  
    }
52.  
    a[i][j].Flag=0;
53.  
    path--;
54.  
    return false;
55.  
    }
56.  
    int main()
57.  
    {
58.  
    scanf("%d%d",&n,&m);
59.  
    for(int p=0; p<=2; p )
60.  
    {
61.  
    scanf("%d",&x[p]);
62.  
    }
63.  
    for(int i=1; i<=n; i )
64.  
    {
65.  
    for(int j=1; j<=m; j )
66.  
    {
67.  
    scanf("%d",&a[i][j].value);
68.  
    a[i][j].Flag=0;
69.  
    }
70.  
    }
71.  
    dfs(1,1);
72.  
    if(flag==1)
73.  
    {
74.  
    for(int k=1; k<=path; k )
75.  
    {
76.  
    printf("%c",b[k]);
77.  
    }
78.  
    }
79.  
    else
80.  
    {
81.  
    printf("-1");
82.  
    }
83.  
    return 0;
84.  
    }

这篇好文章是转载于：学新通技术网