CERK07- SPOJ - bfs 中的位掩码

Question

我正在尝试解决 SPOJ 的问题 CERK07- KeyTask。我在这里使用 bfs 中的位掩码学到了一个新概念。我正在尝试在 java 中实现我的代码。我在 else if(val == 'R'|| val == 'G' || val == 'B' || val =='Y') 条件下遇到问题（即当我遇到一扇门时），我想检查是否有那扇门的钥匙。我的智能 IDE 表明条件 case 'B': if((umask & 0x2) == 1 ) 始终为假。对于低于此条件的所有其他门，情况相同。我不知道为什么会这样？

 public static int bfs(int[] start, char[][] grid, int[][][] d) {
        int m = grid.length;
        int n = grid[0].length;

        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{start[0], start[1], 0});

        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int x = curr[0];
            int y = curr[1];
            int umask = curr[2];
            final int[][] shifts = {
                    {-1, 0},
                    {0, 1},
                    {1, 0},
                    {0, -1}
            };
            for (int[] shift : shifts) {
                int dx = x + shift[0];
                int dy = y + shift[1];

                if (isValid(dx, dy, m, n) && grid[dx][dy] != '#') {
                    if (grid[dx][dy] == 'X') {
                        return d[x][y][umask] + 1;
                    }
                    if (d[dx][dy][umask] == -1) {
                        char val = grid[dx][dy];
                        if (val == 'r' || val == 'b' || val == 'g' || val == 'y') {
                            int vmask = umask;
                            if (val == 'r') vmask |= 0x1;
                            else if (val == 'b') vmask |= 0x2;
                            else if (val == 'g') vmask |= 0x4;
                            else vmask |= 0x8;

                            q.add(new int[]{dx, dy, vmask});
                            d[dx][dy][umask] = d[x][y][umask] + 1;
                            d[dx][dy][vmask] = d[dx][dy][umask];
                        } else if (val == 'R' || val == 'G' || val == 'B' || val == 'Y') {
                            switch (val) {
                                case 'R':
                                    if ((umask & 0x1) == 1) q.add(new int[]{dx, dy, umask});
                                    break;
                                case 'B':
                                    if ((umask & 0x2) == 1) q.add(new int[]{dx, dy, umask});
                                    break;
                                case 'G':
                                    if ((umask & 0x4) == 1) q.add(new int[]{dx, dy, umask});
                                    break;
                                case 'Y':
                                    if ((umask & 0x8) == 1) q.add(new int[]{dx, dy, umask});
                                    break;
                            }
                            d[dx][dy][umask] = d[x][y][umask] + 1;
                        } else {
                            q.add(new int[]{dx, dy, umask});
                            d[dx][dy][umask] = d[x][y][umask] + 1;
                        }
                    }
                }
            }
        }
        return -1;
    }

Answer 1

(umask & 0x2) 表达式的结果是 0 或 2。它不能是 1，因此 IntelliJ IDEA 会警告您这一点。类似地，(umask & 0x4) 是 0 或 4，(umask & 0x8) 是 0 或 8。您可能想写 (umask & 0x2) == 2 等等。这样你的情况就正确了，警告也消失了。

CERK07- SPOJ - bfs 中的位掩码

CERK07- SPOJ - bitmask in bfs

java

graph

breadth-first-search

bitmask

intellij-idea