Check if There is a Valid Path in a Grid

Description

Given a m x n grid. Each cell of the grid represents a street. The street of grid[i][j] can be:

• 1 which means a street connecting the left cell and the right cell.
• 2 which means a street connecting the upper cell and the lower cell.
• 3 which means a street connecting the left cell and the lower cell.
• 4 which means a street connecting the right cell and the lower cell.
• 5 which means a street connecting the left cell and the upper cell.
• 6 which means a street connecting the right cell and the upper cell.

You will initially start at the street of the upper-left cell (0,0). A valid path in the grid is a path which starts from the upper left cell (0,0) and ends at the bottom-right cell (m - 1, n - 1). The path should only follow the streets.

Notice that you are not allowed to change any street.

Return true if there is a valid path in the grid or false otherwise.

 

Example 1:

Input: grid = [[2,4,3],[6,5,2]]
Output: true
Explanation: As shown you can start at cell (0, 0) and visit all the cells of the grid to reach (m - 1, n - 1).

Example 2:

Input: grid = [[1,2,1],[1,2,1]]
Output: false
Explanation: As shown you the street at cell (0, 0) is not connected with any street of any other cell and you will get stuck at cell (0, 0)

Example 3:

Input: grid = [[1,1,2]]
Output: false
Explanation: You will get stuck at cell (0, 1) and you cannot reach cell (0, 2).

Example 4:

Input: grid = [[1,1,1,1,1,1,3]]
Output: true

Example 5:

Input: grid = [[2],[2],[2],[2],[2],[2],[6]]
Output: true

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• 1 <= grid[i][j] <= 6

Solution(javascript)

/* eslint-disable no-loop-func */
// /** DFS Maximum call stack size exceeded
//  * @param {number[][]} grid
//  * @return {boolean}
//  */
// const hasValidPath = function (grid) {
//   const visited = grid.map(items => items.map(() => false))
//   const isValidPosition = (row, column) => {
//     if (
//       row < 0 || row > grid.length - 1
//       || column < 0 || column > grid[row].length - 1
//       || visited[row][column]
//     ) {
//       return false
//     }
//     return true
//   }
//   const isType = (row, colum, types = []) => isValidPosition(row, colum)
//   && types.some(type => type === grid[row][colum])
//   const canGoRight = (row, column) => isType(row, column, [1, 3, 5])
//   const canGoLeft = (row, column) => isType(row, column, [1, 4, 6])
//   const canGoDown = (row, column) => isType(row, column, [2, 5, 6])
//   const canGoUp = (row, colum) => isType(row, colum, [2, 3, 4])

//   const dfs = (row, column) => {
//     if (row === grid.length - 1 && column === grid[row].length - 1) {
//       return true
//     }
//     let valid = false
//     visited[row][column] = true
//     if (grid[row][column] === 1) {
//       if (isValidPosition(row, column + 1) && canGoRight(row, column + 1) && dfs(row, column + 1)) {
//         valid = true
//       }
//       if (isValidPosition(row, column - 1) && canGoLeft(row, column - 1) && dfs(row, column - 1)) {
//         valid = true
//       }
//     } else if (grid[row][column] === 2) {
//       if (isValidPosition(row + 1, column) && canGoDown(row + 1, column) && dfs(row + 1, column)) {
//         valid = true
//       }
//       if (isValidPosition(row - 1, column) && canGoUp(row - 1, column) && dfs(row - 1, column)) {
//         valid = true
//       }
//     } else if (grid[row][column] === 3) {
//       if (isValidPosition(row + 1, column) && canGoDown(row + 1, column) && dfs(row + 1, column)) {
//         valid = true
//       }
//       if (isValidPosition(row, column - 1) && canGoLeft(row, column - 1) && dfs(row, column - 1)) {
//         valid = true
//       }
//     } else if (grid[row][column] === 4) {
//       if (isValidPosition(row + 1, column) && canGoDown(row + 1, column) && dfs(row + 1, column)) {
//         valid = true
//       }
//       if (isValidPosition(row, column + 1) && canGoRight(row, column + 1) && dfs(row, column + 1)) {
//         valid = true
//       }
//     } else if (grid[row][column] === 5) {
//       if (isValidPosition(row - 1, column) && canGoUp(row - 1, column) && dfs(row - 1, column)) {
//         valid = true
//       }
//       if (isValidPosition(row, column - 1) && canGoLeft(row, column - 1) && dfs(row, column - 1)) {
//         valid = true
//       }
//     } else if (grid[row][column] === 6) {
//       if (isValidPosition(row - 1, column) && canGoUp(row - 1, column) && dfs(row - 1, column)) {
//         valid = true
//       }
//       if (isValidPosition(row, column + 1) && canGoRight(row, column + 1) && dfs(row, column + 1)) {
//         valid = true
//       }
//     }
//     return valid
//   }
//   dfs(0, 0)
//   console.log(visited)
// }


/** BFS Maximum call stack size exceeded
 * @param {number[][]} grid
 * @return {boolean}
 */
const hasValidPath = function (grid) {
  const visited = grid.map(items => items.map(() => false))
  const isValidPosition = (row, column) => {
    if (
      row < 0
      || row > grid.length - 1
      || column < 0
      || column > grid[row].length - 1
      || visited[row][column]
    ) {
      return false
    }
    return true
  }
  const isType = (row, column, types = []) => isValidPosition(row, column)
    && types.includes(grid[row][column])
  const canGoRight = (row, column) => isType(row, column, [1, 3, 5])
  const canGoLeft = (row, column) => isType(row, column, [1, 4, 6])
  const canGoDown = (row, column) => isType(row, column, [2, 5, 6])
  const canGoUp = (row, colum) => isType(row, colum, [2, 3, 4])

  const dirMap = {
    1: { left: true, right: true },
    2: { top: true, down: true },
    3: { left: true, down: true },
    4: { right: true, down: true },
    5: { left: true, top: true },
    6: { top: true, right: true },
  }
  let current = [[0, 0]]
  while (current.length > 0) {
    const next = []
    current.forEach(([row, column]) => {
      if (isValidPosition(row, column)) {
        visited[row][column] = true
        const {
          top, down, left, right,
        } = dirMap[grid[row][column]]

        if (left && canGoLeft(row, column - 1)) {
          next.push([row, column - 1])
        }
        if (right && canGoRight(row, column + 1)) {
          next.push([row, column + 1])
        }
        if (top && canGoUp(row - 1, column)) {
          next.push([row - 1, column])
        }
        if (down && canGoDown(row + 1, column)) {
          next.push([row + 1, column])
        }
      }
    })
    current = next
  }
  return visited[grid.length - 1][grid[0].length - 1]
}