Problem Statement

You are given an m*n grid where:

• 1 represents the starting square.
• 2 represents the ending square.
• 0 represents an empty square that you can walk over.
• -1 represents an obstacle that you cannot walk over.

Your task is to find the number of unique paths from the starting square to the ending square, such that:

• You visit every non-obstacle square exactly once.
• You can only move up, down, left, or right (not diagonals).

LeetCode

• https://leetcode.com/problems/unique-paths-iii/description/

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.

Examples

Example 1:

Input:
 grid = [
               [1, 0, 0, 0],
               [0, 0, 0, 0],
               [0, 0, 2, -1]
              ]
Output: 2

Explanation: There are two unique paths from 1 to 2 that visit every 0 once.
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 = [
               [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.

Different Approaches

1️⃣Backtracking (DFS + Visited Matrix)

We use Depth-First Search (DFS) to explore all possible paths from the start cell to the end cell. At each step:

• We mark the cell visited,

• Recursively explore 4 directions,

• Unmark the cell (backtrack),

• Only count the path if we reach the end and have visited all non-obstacle squares exactly once.

Code:

class Solution {
public:
    // Direction vectors: up, left, down, right
    int dimX[4] = {-1, 0, 1, 0};
    int dimY[4] = {0, -1, 0, 1};

    // Utility to check if the cell is within bounds
    bool isValid(int row, int col, int n, int m) {
        return !(row < 0 || row >= n || col < 0 || col >= m);
    }

    // Recursive backtracking function
    int backtrack(vector<vector<int>>& grid, int row, int col, int endX, int endY, int n, int m,
                  vector<vector<bool>>& vis, int safePathCount) {
        
        // ✅ Base case: reached end with all safe squares visited
        if (row == endX && col == endY && safePathCount == 0) {
            return 1;
        }

        int count = 0;

        // Explore 4 directions
        for (int i = 0; i < 4; i++) {
            int newRow = row + dimX[i];
            int newCol = col + dimY[i];

            // Check bounds, not visited, and not an obstacle
            if (isValid(newRow, newCol, n, m) && !vis[newRow][newCol] && grid[newRow][newCol] != -1) {
                vis[newRow][newCol] = true; // mark as visited
                count += backtrack(grid, newRow, newCol, endX, endY, n, m, vis, safePathCount - 1);
                vis[newRow][newCol] = false; // backtrack
            }
        }

        return count;
    }

    int uniquePathsIII(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        int safePathCount = 0; // Count of non-obstacle cells to visit
        int startX = 0, startY = 0, endX = 0, endY = 0;

        // Step 1: Identify start, end, and count safe squares
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < m; col++) {
                if (grid[row][col] != -1) {
                    safePathCount++; // includes start and end
                }
                if (grid[row][col] == 1) {
                    startX = row;
                    startY = col;
                }
                if (grid[row][col] == 2) {
                    endX = row;
                    endY = col;
                }
            }
        }

        // Step 2: Initialize visited matrix and mark start visited
        vector<vector<bool>> vis(n, vector<bool>(m, false));
        vis[startX][startY] = true;

        // Step 3: Start DFS with one cell already visited
        return backtrack(grid, startX, startY, endX, endY, n, m, vis, safePathCount - 1);
    }
};

Complexity Analysis:

• Time Complexity:O(4^k), where k is non-obstacle cells
  • Each cell is branching in 4 directions
• Space Complexity:O(n*m)
  • O(n*m): for the visited matrix
  • O(k): for recursion stack, where k is number of non-obstacle cells