Finance[US] Career Guide Free Tutorials Go to Your University Placement Preparation 
0 like 0 dislike
in Coding Questions by Goeduhub's Expert (2.3k points)

On a 2-dimensional grid, there are 4 types of squares:

  • 1 represents the starting square.  There is exactly one starting square.
  • 2 represents the ending square.  There is exactly one ending square.
  • 0 represents empty squares we can walk over.
  • -1 represents 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: [[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: [[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: [[0,1],[2,0]]
Output: 0
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.



  1. 1 <= grid.length * grid[0].length <= 20

1 Answer

0 like 0 dislike
by Goeduhub's Expert (2.3k points)
Best answer


We can consider backtracking as a state machine, where we start off from an initial state, each action we take will move the state from one to another, and there should be some final state where we reach our goal.

As a result, let us first clarify the initial and the final states of the problem.

  • Initial State

    • There are different types of squares/cells in a grid.

    • There are an origin and a destination cell, which are not given explicitly.

    • Initially, all the cells are not visited.

  • Final State

    • We reach the destination cell, i.e. cell filled with the value 2.

    • We have visited all the non-obstacle cells, including the empty cells (i.e. filled with 0) and the initial cell (i.e. 1).

With the above definition, we can then translate the problem as finding all paths that can lead us from the initial state to the final state.

state machine

More specifically, we could summarise the steps to implement the backtracking algorithm for this problem in the following pseudo code.

    def backtrack(cell):
        1. if we arrive at the final state:
             path_count ++

        2. mark the current cell as visited

        3. for next_cell in 4 directions:
             if next_cell is not visited and non-obstacle:

        4. unmark the current cell



As one can see, backtracking is more of a methodology to solve a specific type of problems. For a backtracking problem, it would not be exaggerating to say that there are a thousand backtracking implementations in a thousand people's eyes, as one would find out in the implementation later.

class Solution:

    def uniquePathsIII(self, grid: List[List[int]]) -> int:

        rows, cols = len(grid), len(grid[0])

        # step 1). initialize the conditions for backtracking

        #   i.e. initial state and final state

        non_obstacles = 0

        start_row, start_col = 0, 0

        for row in range(0, rows):

            for col in range(0, cols):

                cell = grid[row][col] 

                if  cell >= 0:

                    non_obstacles += 1

                if cell == 1:

                    start_row, start_col = row, col

        # count of paths as the final result

        path_count = 0

        # step 2). backtrack on the grid

        def backtrack(row, col, remain):

            # we need to modify this external variable

            nonlocal path_count

            # base case for the termination of backtracking

            if grid[row][col] == 2 and remain == 1:

                # reach the destination

                path_count += 1


            # mark the square as visited. case: 0, 1, 2 

            temp = grid[row][col] 

            grid[row][col] = -4

            remain -= 1   # we now have one less square to visit

            # explore the 4 potential directions around

            for ro, co in [(0, 1), (0, -1), (1, 0), (-1, 0)]:

                next_row, next_col = row + ro, col + co

                if not (0 <= next_row < rows and 0 <= next_col < cols):

                    # invalid coordinate


                if grid[next_row][next_col] < 0:

                    # either obstacle or visited square


                backtrack(next_row, next_col, remain)

            # unmark the square after the visit

            grid[row][col] = temp

        backtrack(start_row, start_col, non_obstacles)

        return path_count

eg : grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]

ans = Solution()


Output -


Learn & Improve In-Demand Data Skills Online in this Summer With  These High Quality Courses[Recommended by GOEDUHUB]:-

Best Data Science Online Courses[Lists] on:-

Claim your 10 Days FREE Trial for Pluralsight.

Best Data Science Courses on Datacamp
Best Data Science Courses on Coursera
Best Data Science Courses on Udemy
Best Data Science Courses on Pluralsight
Best Data Science Courses & Microdegrees on Udacity
Best Artificial Intelligence[AI] Courses on Coursera
Best Machine Learning[ML] Courses on Coursera
Best Python Programming Courses on Coursera
Best Artificial Intelligence[AI] Courses on Udemy
Best Python Programming Courses on Udemy

Related questions

0 like 0 dislike
1 answer 250 views
asked Sep 13, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)
0 like 0 dislike
1 answer 1.7k views
asked Sep 10, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)
0 like 0 dislike
1 answer 2.6k views
0 like 0 dislike
1 answer 256 views
0 like 0 dislike
1 answer 981 views

 Important Lists:

Important Lists, Exams & Cutoffs Exams after Graduation PSUs


About Us | Contact Us || Terms & Conditions | Privacy Policy ||  Youtube Channel || Telegram Channel © Social::   |  | 


Free Online Directory