1926迷宫中离入口最近的出口

给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 ‘.’ 表示）和墙（用 ‘+’ 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。

每一步操作，你可以往上，下，左或者右移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近的出口。出口的含义是 maze 边界上的空格子。entrance 格子不算出口。

请你返回从 entrance 到最近出口的最短路径的步数，如果不存在这样的路径，请你返回 -1 。

示例 1：

输入：maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
输出：1
解释：总共有 3 个出口，分别位于 (1,0)，(0,2) 和 (2,3) 。
一开始，你在入口格子 (1,2) 处。
- 你可以往左移动 2 步到达 (1,0) 。
- 你可以往上移动 1 步到达 (0,2) 。
从入口处没法到达 (2,3) 。
所以，最近的出口是 (0,2) ，距离为 1 步。

示例 2：

输入：maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
输出：2
解释：迷宫中只有 1 个出口，在 (1,2) 处。
(1,0) 不算出口，因为它是入口格子。
初始时，你在入口与格子 (1,0) 处。
- 你可以往右移动 2 步到达 (1,2) 处。
所以，最近的出口为 (1,2) ，距离为 2 步。

示例 3：

输入：maze = [[".","+"]], entrance = [0,0]
输出：-1
解释：这个迷宫中没有出口。

提示：

maze.length == m
maze[i].length == n
1 <= m, n <= 100
maze[i][j] 要么是 ‘.’ ，要么是 ‘+’ 。
entrance.length == 2
0 <= entrancerow < m
0 <= entrancecol < n
entrance 一定是空格子。

Solution 1

class Solution {
    public int nearestExit(char[][] maze, int[] entrance) {
        maze[entrance[0]][entrance[1]] = 'e';
        boolean canExit = false, canGo = true;
        int cnt = 0;
        while (!(canExit || !canGo)) {
            // if (canExit) {break;}
            // if (!canGo) {break;}
            canGo = goOnce(maze);
            cnt++;
            canExit = visitedBoarder(maze);
        }
        if (!canExit && !canGo) {
            return -1;
        }
        return cnt;
    }

    boolean goOnce(char[][] maze) {
        int rowNum = maze.length, colNum = maze[0].length;
        int cnt = 0;
        for (int i = 0; i < rowNum; i++) {
            for (int j = 0; j < colNum; j++) {
                if (maze[i][j] == '=' || maze[i][j] == 'e') {
                    // + wall // . road // - going // = gone
                    if (i - 1 >= 0 && maze[i - 1][j] == '.') {
                        maze[i - 1][j] = '-';
                        cnt++;
                    }
                    if (i + 1 < rowNum && maze[i + 1][j] == '.') {
                        maze[i + 1][j] = '-';
                        cnt++;
                    }
                    if (j - 1 >= 0 && maze[i][j - 1] == '.') {
                        maze[i][j - 1] = '-';
                        cnt++;
                    }
                    if (j + 1 < colNum && maze[i][j + 1] == '.') {
                        maze[i][j + 1] = '-';
                        cnt++;
                    }
                }
            }
        }
        for (int i = 0; i < rowNum; i++) {
            for (int j = 0; j < colNum; j++) {
                if (maze[i][j] == '-') {
                    maze[i][j] = '=';
                }
            }
        }
        return cnt != 0;
    }

    boolean visitedBoarder(char[][] maze) {
        boolean visited = false;
        int rowNum = maze.length, colNum = maze[0].length;
        for (int i = 0; i < rowNum; i++) {
            if (maze[i][0] == '=' || maze[i][colNum - 1] == '=') {
                visited = true;
            }
        }
        for (int j = 0; j < colNum; j++) {
            if (maze[0][j] == '=' || maze[rowNum - 1][j] == '=') {
                visited = true;
            }
        }
        return visited;
    }
}