# 1778. Shortest Path in a Hidden Grid¶

• Time: $O(m^2)$
• Space: $O(m^2)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 /** * // This is the GridMaster's API interface. * // You should not implement it, or speculate about its implementation * class GridMaster { * public: * bool canMove(char direction); * void std::move(char direction); * boolean isTarget(); * }; */ enum class Grid { kUnvisited, kStart, kTarget, kBlocked, kEmpty }; class Solution { public: int findShortestPath(GridMaster& master) { constexpr int m = 500; constexpr int startX = m; constexpr int startY = m; vector> grid(m * 2, vector(m * 2, Grid::kUnvisited)); // Build the grid information by DFS. dfs(master, grid, startX, startY); int ans = 0; queue> q{{{startX, startY}}}; grid[startX][startY] = Grid::kBlocked; // Find the steps by BFS. while (!q.empty()) { ++ans; for (int sz = q.size(); sz > 0; --sz) { const auto [i, j] = q.front(); q.pop(); for (const auto& [dx, dy] : dirs) { const int x = i + dx; const int y = j + dy; if (grid[x][y] == Grid::kTarget) return ans; if (grid[x][y] == Grid::kBlocked) continue; grid[x][y] = Grid::kBlocked; q.emplace(x, y); } } } return -1; } private: static constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; static constexpr char charTable[4] = {'R', 'D', 'L', 'U'}; void dfs(GridMaster& master, vector>& grid, int i, int j) { if (grid[i][j] != Grid::kUnvisited) return; if (master.isTarget()) grid[i][j] = Grid::kTarget; else grid[i][j] = Grid::kEmpty; for (int k = 0; k < 4; ++k) { const int x = i + dirs[k][0]; const int y = j + dirs[k][1]; const char d = charTable[k]; const char undoD = charTable[(k + 2) % 4]; if (master.canMove(d)) { master.std::move(d); dfs(master, grid, x, y); master.std::move(undoD); } else { grid[x][y] = Grid::kBlocked; } } } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 /** * // This is the GridMaster's API interface. * // You should not implement it, or speculate about its implementation * class GridMaster { * boolean canMove(char direction); * void move(char direction); * boolean isTarget(); * }; */ enum Grid { kUnvisited, kStart, kTarget, kBlocked, kEmpty } class Solution { public int findShortestPath(GridMaster master) { final int m = 500; final int startX = m; final int startY = m; Grid[][] grid = new Grid[m * 2][m * 2]; Arrays.stream(grid).forEach(A -> Arrays.fill(A, Grid.kUnvisited)); // Build the grid information by DFS. dfs(master, grid, startX, startY); int ans = 0; Queue q = new ArrayDeque<>(); q.offer(new int[] {startX, startY}); grid[startX][startY] = Grid.kBlocked; // Find the steps by BFS. while (!q.isEmpty()) { ++ans; for (int sz = q.size(); sz > 0; --sz) { final int i = q.peek()[0]; final int j = q.poll()[1]; for (int[] dir : dirs) { final int x = i + dir[0]; final int y = j + dir[1]; if (grid[x][y] == Grid.kTarget) return ans; if (grid[x][y] == Grid.kBlocked) continue; grid[x][y] = Grid.kBlocked; q.offer(new int[] {x, y}); } } } return -1; } private static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; private static final char[] charTable = {'R', 'D', 'L', 'U'}; private void dfs(GridMaster master, Grid[][] grid, int i, int j) { if (grid[i][j] != Grid.kUnvisited) return; if (master.isTarget()) grid[i][j] = Grid.kTarget; else grid[i][j] = Grid.kEmpty; for (int k = 0; k < 4; ++k) { final int x = i + dirs[k]; final int y = j + dirs[k + 1]; final char d = charTable[k]; final char undoD = charTable[(k + 2) % 4]; if (master.canMove(d)) { master.move(d); dfs(master, grid, x, y); master.move(undoD); } else { grid[x][y] = Grid.kBlocked; } } } }