侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 29 条评论

目 录CONTENT

文章目录

【DFS】密室逃脱

GabrielxD
2023-04-15 / 0 评论 / 0 点赞 / 396 阅读 / 1,059 字
温馨提示:
本文最后更新于 2023-04-15,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

试题 算法提高 密室逃脱


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

  • “红魔法”(r):瞬间移动到所在房间右边的第二间房;
  • “绿魔法”(g):瞬间移动到所在房间右下方的房间;
  • “蓝魔法”(b):瞬间移动到所在房间下方的第三间房;

魔法师小L最近也迷上了这款游戏,他在游戏开始前拿到了房间地图(“安全的”房间用1标记,“危险的”房间用0标记),并被告知只能使用 aa 次红魔法, bb 次绿魔法和 cc 次蓝魔法(数据保证 n=1+b+3×cn=1+b+3\times cm=1+b+2×am=1+b+2\times a ),那么请聪明的你告诉小L,他能不能胜利?如果可以,该怎么使用魔法才能安全的到达右下角的房间?

输入

输入第一行为五个整数 n,m,a,b,cn, m, a, b, c ,用空格隔开;

第二行到第 n+1n+1 行每行 mm 个整数( 0011 ),表示房间地图(数据保证地图左上角和右下角的整数为 11

输出

若小L不能够到达终点,则输出 1-1

若小L能够到达终点,则输出字典序最大的使用的魔法序列(用 r,g,br, 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

数据规模和约定

  • 1nm10001≤n,m≤1000

解题

方法一:DFS

思路

DFS,按字典序( r>g>br > 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);
    }
}
0

评论区