【DFS】密室逃脱

题目

试题 算法提高 密室逃脱

---

真人版密室逃脱游戏风靡全球，不仅在麻瓜世界广受欢迎，而且在魔法世界也十分流行。考虑到魔法世界的人们会使用能够瞬间移动的魔法，密室逃脱游戏在被引进魔法世界时作了一些修改：“密室迷宫”由排成 $n$ 行 $m$ 列的 $nm$ 间房间组成，每间房间会被标记为“危险的”或者“安全的”，参加者在左上角的房间中开始游戏，通过使用红绿蓝三种不同的魔法在房间迷阵中移动（只能移动到“安全的”房间，不能移动到“危险的”房间），最后到达右下角的房间即获得胜利。三种不同魔法的效果如下：

• “红魔法”（r）：瞬间移动到所在房间右边的第二间房；
• “绿魔法”（g）：瞬间移动到所在房间右下方的房间；
• “蓝魔法”（b）：瞬间移动到所在房间下方的第三间房；

魔法师小L最近也迷上了这款游戏，他在游戏开始前拿到了房间地图（“安全的”房间用1标记，“危险的”房间用0标记），并被告知只能使用 $a$ 次红魔法， $b$ 次绿魔法和 $c$ 次蓝魔法（数据保证 $n=1+b+3\times c$ ；$m=1+b+2\times 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$

解题

方法一：DFS

思路

DFS，按字典序（ $r > g > b$ ）尝试行走方向，找到的第一条合法路线就是字典序最大的魔法序列。

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int[][] DIRS = {{0, 2}, {1, 1}, {3, 0}};
    static final char[] DIRCS = {'r', 'g', 'b'};
    static int n, m;
    static StringBuilder path = new StringBuilder();
    static int[][] g;
    static boolean found = false;

    static void dfs(int x, int y, int[] maho) {
        if (found) return;
        if (x == n - 1 && y == m - 1) {
            System.out.println(path);
            found = true;
            return;
        }
        for (int i = 0; i < 3; ++i) {
            if (maho[i] == 0) continue;
            int nx = x + DIRS[i][0], ny = y + DIRS[i][1];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m || g[nx][ny] == 0) continue;
            --maho[i];
            path.append(DIRCS[i]);
            dfs(nx, ny, maho);
            path.deleteCharAt(path.length() - 1);
            ++maho[i];
        }
    }

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken(); n = (int) in.nval;
        in.nextToken(); m = (int) in.nval;
        in.nextToken(); int a = (int) in.nval;
        in.nextToken(); int b = (int) in.nval;
        in.nextToken(); int c = (int) in.nval;
        g = new int[n][m];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                in.nextToken(); g[i][j] = (int) in.nval;
            }
        }
        dfs(0, 0, new int[]{a, b, c});
        if (!found) System.out.println(-1);
    }
}