个人中心
gpt4 book ai didi

java - 如何在带 key 和门的谜题中找到最短路径

转载 作者：塔克拉玛干 更新时间：2023-11-02 08:05:12 24 4
gpt4 key购买 nike

我试过下面的代码，但它没有给我正确的答案。

这是问题陈述。

Suppose you have a 2-D grid. Each point is either land or water. There is also a start point and a goal.

There are now keys that open up doors. Each key corresponds to one door.

Implement a function that returns the shortest path from the start to the goal using land tiles, keys and open doors.

Data Representation

The map will be passed as an array of strings.

A map can have the following tiles.

0 = Water 1 = Land 2 = Start 3 = Goal uppercase = door lowercase = key

The grid can be like this:

            {{'0', '2', '1', '1', '1'},
            {'0', '1', '0', '0', '1'},
            {'0', '0', '0', '0', '1'},
            {'0', '0', 'A', '0', '1'},
            {'1', '1', 'a', '1', '1'},
            {'1', 'b', '0', '0', 'B'},
            {'1', '1', '0', '0', '1'},
            {'0', '1', '0', '0', '3'}};

So the shortest path should be: 01->02->03->04->14->24->34->44->43->42->41->51->41->42->43->44->54->64->74

我的代码是这样的:

public class shortestPath {
    static int shortest = Integer.MAX_VALUE;
    static String path = "";
    static ArrayList<ArrayList<int[]>> res = new ArrayList<ArrayList<int[]>>();

    public static void main(String[] args) {
        char[][] board = {{'0', '2', '1', '1', '1'},
                {'0', '1', '0', '0', '1'},
                {'0', '0', '0', '0', '1'},
                {'0', '0', 'A', '0', '1'},
                {'1', '1', 'a', '1', '1'},
                {'1', 'b', '0', '0', 'B'},
                {'1', '1', '0', '0', '1'},
                {'0', '1', '0', '0', '3'}};
        System.out.println(findShortest(board));
        System.out.println(path);

    }

    public static int findShortest(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) return 0;
        int row = board.length;
        int col = board[0].length;
        int[] start = new int[2];
        int[] end = new int[2];
        int[][] visited = new int[row][col];
        HashMap<Character, ArrayList<int[]>> hm = new HashMap<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == '2') {
                    start = new int[]{i, j};
                }
                if (board[i][j] == '3') {
                    end = new int[]{i, j};
                }
                if (Character.isUpperCase(board[i][j])) {
                    char key = Character.toLowerCase(board[i][j]);
                    if (hm.containsKey(key)) {
                        hm.get(key).add(new int[]{i, j});
                    } else {
                        ArrayList<int[]> al = new ArrayList<>();
                        al.add(new int[]{i, j});
                        hm.put(key, al);
                    }
                    board[i][j] = '0';
                }
            }
        }
        //HashSet<Character> hs = new HashSet<Character>();
        //helper2(board, hs, start[0], start[1], row, col, 0, visited, new StringBuilder(), new ArrayList<int[]>(), res);
        helper(board, hm, start[0], start[1], row, col, 0, visited, new StringBuilder());
        return shortest;
    }

    public static void helper(char[][] board, HashMap<Character, ArrayList<int[]>> hm, int r, int c, int row, int col, int count, int[][] visited, StringBuilder sb) {
        // System.out.println(r + " " + c);
        visited[r][c] = visited[r][c] + 1;
        sb.append(r).append(c).append("->");
        if (board[r][c] == '3') {
            System.out.println(count);
            if (shortest > count) {
                path = sb.deleteCharAt(sb.length() - 1).deleteCharAt(sb.length() - 1).toString();
                sb.append("->");
                shortest = count;
            }
            //return;
            //shortest = Math.min(shortest, count);
        }
        if (Character.isLowerCase(board[r][c])) {  // if this is the key;
            if (hm.containsKey(board[r][c])) {
                for (int[] i : hm.get(board[r][c])) {
                    board[i[0]][i[1]] = '1';
                }
            }
        }
        if (r + 1 < row && board[r + 1][c] != '0' && visited[r + 1][c] < 2) {
            helper(board, hm, r + 1, c, row, col, count + 1, visited, sb);
        }
        if (c + 1 < col && board[r][c + 1] != '0' && visited[r][c + 1] < 2) {
            helper(board, hm, r, c + 1, row, col, count + 1, visited, sb);
        }
        if (r - 1 >= 0 && board[r - 1][c] != '0' && visited[r - 1][c] < 2) {
            helper(board, hm, r - 1, c, row, col, count + 1, visited, sb);
        }
        if (c - 1 >= 0 && board[r][c - 1] != '0' && visited[r][c - 1] < 2) {
            helper(board, hm, r, c - 1, row, col, count + 1, visited, sb);
        }
        visited[r][c] = visited[r][c] - 1;
        sb.delete(sb.length() - 4, sb.length());
        if (Character.isLowerCase(board[r][c])) {  // if this is the key;
            if (hm.containsKey(board[r][c])) {
                for (int[] i : hm.get(board[r][c])) {
                    board[i[0]][i[1]] = '0';
                }
            }
        }
        return;
    }


}

最佳答案

您的问题是 visited 跟踪和锁门跟踪 (由 hm 变量管理，这是一个非常糟糕的名称)的错误实现的组合，因为名称无助于理解变量是什么/做什么)。

访问跟踪

您的小机器人经常一遍又一遍地来回走动。例如，如果您插入用于调试的打印语句:

  • 跟踪并打印尝试前进的总步数
  • 只要找到更短的路径，就打印到达目标的最短路径
  • 每当找到更长的路径时打印尝试的最长路径

您会得到以下结果，其中 ! 表示走的路径较长，而 * 表示找到目标的路径较短:

     1: ! 01->
     2: ! 01->11->
     3: ! 01->11->01->
     4: ! 01->11->01->11->
     6: ! 01->11->01->02->03->
     7: ! 01->11->01->02->03->04->
     8: ! 01->11->01->02->03->04->14->
     9: ! 01->11->01->02->03->04->14->24->
    10: ! 01->11->01->02->03->04->14->24->34->
    11: ! 01->11->01->02->03->04->14->24->34->44->
    12: ! 01->11->01->02->03->04->14->24->34->44->34->
    13: ! 01->11->01->02->03->04->14->24->34->44->34->44->
    14: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->
    15: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->
    16: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->
    17: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->
    18: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->32->
    20: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->
    21: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->
    22: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->
    23: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->
    24: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->71->
    26: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->51->41->
    27: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->51->41->40->
    28: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->51->41->40->50->
    29: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->51->41->40->50->60->
    30: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->51->41->40->50->60->50->
    31: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->51->41->40->50->60->50->60->
  9577: * 01->11->01->02->03->04->14->24->34->44->43->42->41->51->61->71->61->51->41->42->43->44->54->64->74->
  9611: ! 01->11->01->02->03->04->14->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->
  9612: ! 01->11->01->02->03->04->14->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->64->
  9613: ! 01->11->01->02->03->04->14->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->64->74->
  9623: ! 01->11->01->02->03->04->14->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->34->24->14->04->03->02->
  9901: * 01->11->01->02->03->04->14->24->34->44->43->42->41->51->61->51->41->42->43->44->54->64->74->
 19141: ! 01->11->01->02->03->04->14->24->34->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->64->74->
 53941: ! 01->11->01->02->03->04->14->04->14->24->34->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->64->
 53942: ! 01->11->01->02->03->04->14->04->14->24->34->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->64->74->
145776: ! 01->11->01->02->03->02->03->04->14->04->14->24->34->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->64->
145777: ! 01->11->01->02->03->02->03->04->14->04->14->24->34->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->64->74->
158937: * 01->02->03->04->14->24->34->44->43->42->41->51->61->51->41->42->43->44->54->64->74->

向前迈出的总步数:390236

那条最长的路要来回走很多路:

01->11->
01->02->03->
    02->03->04->14->
            04->14->24->34->
                    24->34->44->43->42->41->51->61->71->61->
                                            51->50->60->
                                                50->40->41->42->43->44->54->64->74->
                                                                            64->74->

那是浪费了很多步行。

锁门跟踪

回顾一下您的逻辑:您最初将所有门更改为 0(水)。当您遇到一把 key 时，您可以通过将棋盘值更改为 1(土地)来解锁适合该 key 的所有门。回溯时，您将所有门更改回 0(水)。

现在看看您的代码得出的解决方案:

01->02->03->04->14->24->34->44->43->42->41->51->61->
                                            51->41->42->43->44->54->64->74

问题是 key 在 51，所以当代码从那个解决方案回溯到 second 51 时，它会关上门，所以当它回到第一个 51 并尝试从那里直接走到目标时，门是关闭的，即使你有 key 。

那是因为你没有意识到你有两次 key 。

解决方案

如果您只是修复访问过的跟踪，您的代码将起作用，因为您不会两次踩到同一个键。

如果您只是修复锁定的门跟踪，即跟踪您拥有同一把 key 的多个副本，您的代码将起作用，因为您不会再次过早地锁门。

但是，对于您修改后的解决方案，请考虑以下事项:

  • 如果实际上有不止一个相同的 key 怎么办？
  • 不要重复访问某个位置，除非您已拿到新 key 。
  • 如果您所走的路径已经比目前找到的到达目标的最短路径还长，请不要继续走。

因此，一种不同的方法是考虑它在现实生活中的运作方式。当您找到 key 时，您不会打开门，因为 1) 您不一定知道门在哪里，以及 2) 从您所站的位置无法到达门。

相反，保留一个 key 圈。当您遇到您没有的 key 时，将其添加到 key 环中。将新 key 添加到 key 圈还意味着您可以重新访问以前走过的区域。当你遇到一扇门时，如果你的 key 在 key 圈里，你就可以穿过它。

由于有 26 个可能的 key ，一个 32 位的 int 值可以作为您的 key 环。

参见 IDEONE对于仅需要 90 个步骤(而不是当前代码的 390236 个步骤)来检查所有可能/相关路径的示例实现。

关于java - 如何在带 key 和门的谜题中找到最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/39431473/

24 4 0
文章推荐： java - Apache POI 公式未评估
文章推荐： iphone - UIManagedDocument:网络中断时创建新文件时出错/崩溃(保存)
文章推荐： ios - 异步下载图像到 NSData 和缓存
文章推荐： ios - 使用视觉格式化语言在代码中自动布局 UIViewController
塔克拉玛干
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com