兔子逃跑测试 3

public class Solution {
    static class Node {
        int x;
        int y;
        int status;

        public Node(int x, int y, int status) {
            this.x = x;
            this.y = y;
            this.status = status;
        }
    }

    private static int n;
    private static int m;
    private static int[][][] dis;
    private static final int INF = 0x3f3f3f3f;
    private static int[][] G;
    private static Queue<Node> que = new ArrayDeque<>();
    private static final int[][] dir = new int[][]{
            {0, 1}, {0, -1}, {1, 0}, {-1, 0}
    };

    public static int solution(int[][] map) {
        init(map);
        bfs();
        int ans = Math.min(dis[n - 1][m - 1][0], dis[n - 1][m - 1][1]);
        return ans == INF ? -1 : ans;
    }

    private static void init(int[][] map) {
        n = map.length;
        m = map[0].length;
        dis = new int[n][m][2];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                dis[i][j][0] = INF;
                dis[i][j][1] = INF;
            }
        }
        Solution.G = map;

        while (!que.isEmpty()) {
            que.poll();
        }
    }

    private static void bfs() {
        que.add(new Node(0, 0, 0));
        dis[0][0][0] = 1;

        while (!que.isEmpty()) {
            Node tmp = que.poll();
            for (int i = 0; i < 4; ++i) {
                int x = tmp.x + dir[i][0];
                int y = tmp.y + dir[i][1];
                if (!in(x, y) || G[x][y] + tmp.status > 1) {
                    continue;
                }
                if (dis[x][y][tmp.status + G[x][y]] > dis[tmp.x][tmp.y][tmp.status] + 1) {
                    dis[x][y][tmp.status + G[x][y]] = dis[tmp.x][tmp.y][tmp.status] + 1;
                    que.add(new Node(x, y, tmp.status + G[x][y]));
                }
            }
        }
    }

    public static boolean in(int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < m;
    }
}