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

Description

You are given an m x n grid. Each cell of 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 that 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).

 

Constraints:

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

 

Solutions

Solution: Depth-First Search

• Time complexity: O(m*n)
• Space complexity: O(m*n)

 

JavaScript

/**
 * @param {number[][]} grid
 * @return {boolean}
 */
const hasValidPath = function (grid) {
  const m = grid.length;
  const n = grid[0].length;
  const connectMap = { left: 'right', right: 'left', upper: 'lower', lower: 'upper' };
  const moveMap = {
    left: { row: 0, col: -1 },
    right: { row: 0, col: 1 },
    upper: { row: -1, col: 0 },
    lower: { row: 1, col: 0 },
  };
  const streetMap = {
    1: ['left', 'right'],
    2: ['upper', 'lower'],
    3: ['left', 'lower'],
    4: ['lower', 'right'],
    5: ['left', 'upper'],
    6: ['upper', 'right'],
  };
  const isValidPath = (row, col, connect, visited = new Set()) => {
    if (row >= m || col >= n || row < 0 || col < 0) return false;
    if (visited.has(`${row}_${col}`)) return false;
    const street = streetMap[grid[row][col]];
    const startStreet = street.indexOf(connect);
    const isConnect = startStreet !== -1;
    if (!isConnect) return false;
    if (row === m - 1 && col === n - 1) return true;

    const endStreet = startStreet ? street[0] : street[1];
    const move = moveMap[endStreet];
    const nextConnect = connectMap[endStreet];

    visited.add(`${row}_${col}`);
    return isValidPath(row + move.row, col + move.col, nextConnect, visited);
  };
  const [directionA, directionB] = streetMap[grid[0][0]];

  return isValidPath(0, 0, directionA) || isValidPath(0, 0, directionB);
};