DEV Community

Abhishek Chaudhary
Abhishek Chaudhary

Posted on

Unique Paths III

You are given an m x n integer array grid where grid[i][j] could be:

  • 1 representing the starting square. There is exactly one starting square.
  • 2 representing the ending square. There is exactly one ending square.
  • 0 representing empty squares we can walk over.
  • -1 representing obstacles that we cannot walk over.

Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.

Example 1:

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths:

  1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
  2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

Example 2:

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output: 4
Explanation: We have the following four paths:

  1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
  2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
  3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
  4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)

Example 3:

Input: grid = [[0,1],[2,0]]
Output: 0
Explanation: There is no path that walks over every empty square exactly once.
Note that the starting and ending square can be anywhere in the grid.

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 20
  • 1 <= m * n <= 20
  • -1 <= grid[i][j] <= 2
  • There is exactly one starting cell and one ending cell.

SOLUTION:

class Solution:
    def getNeighbors(self, start, m, n):
        a, b = start
        neighbors = []
        if a > 0:
            neighbors.append((a - 1, b))
        if a < m - 1:
            neighbors.append((a + 1, b))
        if b > 0:
            neighbors.append((a, b - 1))
        if b < n - 1:
            neighbors.append((a, b + 1))
        return neighbors

    def unipaths(self, start, grid, visited, m, n, numEmpty):
        currval = grid[start[0]][start[1]]
        ways = 0
        if currval == -1:
            return ways
        if currval == 2:
            if len(visited) == numEmpty + 2:
                return ways + 1
            return ways
        neighbors = self.getNeighbors(start, m, n)
        for neighbor in neighbors:
            if grid[neighbor[0]][neighbor[1]] != -1 and neighbor not in visited:
                ways += self.unipaths(neighbor, grid, visited.union({neighbor}), m, n, numEmpty)
        return ways

    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        numEmpty = 0
        start = None
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    numEmpty += 1
                elif grid[i][j] == 1:
                    start = (i, j)
        return self.unipaths(start, grid, {start}, m, n, numEmpty)
Enter fullscreen mode Exit fullscreen mode

AWS GenAI LIVE image

Real challenges. Real solutions. Real talk.

From technical discussions to philosophical debates, AWS and AWS Partners examine the impact and evolution of gen AI.

Learn more

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay