# 1391. Check if There is a Valid Path in a Grid

• Time: $O(mn)$
• Space: $O(mn)$
  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 class Solution { public: bool hasValidPath(vector>& grid) { const int m = grid.size(); const int n = grid[0].size(); // g := upscaled grid vector> g(m * 3, vector(n * 3)); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) switch (grid[i][j]) { case 1: g[i * 3 + 1][j * 3 + 0] = true; g[i * 3 + 1][j * 3 + 1] = true; g[i * 3 + 1][j * 3 + 2] = true; break; case 2: g[i * 3 + 0][j * 3 + 1] = true; g[i * 3 + 1][j * 3 + 1] = true; g[i * 3 + 2][j * 3 + 1] = true; break; case 3: g[i * 3 + 1][j * 3 + 0] = true; g[i * 3 + 1][j * 3 + 1] = true; g[i * 3 + 2][j * 3 + 1] = true; break; case 4: g[i * 3 + 1][j * 3 + 1] = true; g[i * 3 + 1][j * 3 + 2] = true; g[i * 3 + 2][j * 3 + 1] = true; break; case 5: g[i * 3 + 0][j * 3 + 1] = true; g[i * 3 + 1][j * 3 + 0] = true; g[i * 3 + 1][j * 3 + 1] = true; break; case 6: g[i * 3 + 0][j * 3 + 1] = true; g[i * 3 + 1][j * 3 + 1] = true; g[i * 3 + 1][j * 3 + 2] = true; break; } return dfs(g, 1, 1); } private: bool dfs(vector>& g, int i, int j) { if (i < 0 || i == g.size() || j < 0 || j == g[0].size()) return false; if (!g[i][j]) // no path here return false; if (i == g.size() - 2 && j == g[0].size() - 2) return true; g[i][j] = false; // mark as visited return dfs(g, i + 1, j) || dfs(g, i - 1, j) || dfs(g, i, j + 1) || dfs(g, i, j - 1); } }; 
  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 class Solution { public boolean hasValidPath(int[][] grid) { final int m = grid.length; final int n = grid[0].length; // g := upscaled grid boolean[][] g = new boolean[m * 3][n * 3]; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) switch (grid[i][j]) { case 1: g[i * 3 + 1][j * 3 + 0] = true; g[i * 3 + 1][j * 3 + 1] = true; g[i * 3 + 1][j * 3 + 2] = true; break; case 2: g[i * 3 + 0][j * 3 + 1] = true; g[i * 3 + 1][j * 3 + 1] = true; g[i * 3 + 2][j * 3 + 1] = true; break; case 3: g[i * 3 + 1][j * 3 + 0] = true; g[i * 3 + 1][j * 3 + 1] = true; g[i * 3 + 2][j * 3 + 1] = true; break; case 4: g[i * 3 + 1][j * 3 + 1] = true; g[i * 3 + 1][j * 3 + 2] = true; g[i * 3 + 2][j * 3 + 1] = true; break; case 5: g[i * 3 + 0][j * 3 + 1] = true; g[i * 3 + 1][j * 3 + 0] = true; g[i * 3 + 1][j * 3 + 1] = true; break; case 6: g[i * 3 + 0][j * 3 + 1] = true; g[i * 3 + 1][j * 3 + 1] = true; g[i * 3 + 1][j * 3 + 2] = true; break; } return dfs(g, 1, 1); } private boolean dfs(boolean[][] g, int i, int j) { if (i < 0 || i == g.length || j < 0 || j == g[0].length) return false; if (!g[i][j]) // no path here return false; if (i == g.length - 2 && j == g[0].length - 2) return true; g[i][j] = false; // mark as visited return dfs(g, i + 1, j) || dfs(g, i - 1, j) || dfs(g, i, j + 1) || dfs(g, i, j - 1); } }