A HARD problem to reach 800

Decided to pick a HARD problem as problem #800. Here it is: Unique Paths III - LeetCode

980. Unique Paths III

Hard

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
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.

 

Note:

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

Accepted

65,649

Submissions

85,157

Given the small limits, this then becomes a classic backtracking algorithm. Nothing else really to say, no gotchas or caveats, just standard backtracking. Cheers friends, ACC.

public int UniquePathsIII(int[][] grid)
{
    int startRow = 0;
    int startCol = 0;
    int endRow = 0;
    int endCol = 0;
    int countNonObstacles = 0;
    int countUniquePaths = 0;
    int keyMultiplier = 0;
    Hashtable visited = new Hashtable();

    PreprocessGrid(grid, out startRow, out startCol, out endRow, out endCol, out countNonObstacles, out keyMultiplier);
    int key = startRow * keyMultiplier + startCol;
    visited.Add(key, true);

    ClassicBacktracking(grid, startRow, startCol, endRow, endCol, countNonObstacles, visited, keyMultiplier, ref countUniquePaths);

    return countUniquePaths;
}

private void ClassicBacktracking(int[][] grid,
                                    int currentRow,
                                    int currentCol,
                                    int endRow,
                                    int endCol,
                                    int countNonObstacles,
                                    Hashtable visited,
                                    int keyMultiplier,
                                    ref int countUniquePaths)
{
    if (currentRow == endRow && currentCol == endCol)
    {
        if (visited.Count >= countNonObstacles) countUniquePaths++;
        return;
    }

    int[] rowDelta = { 1, -1, 0, 0 };
    int[] colDelta = { 0, 0, 1, -1 };

    for (int i = 0; i < rowDelta.Length; i++)
    {
        int row = currentRow + rowDelta[i];
        int col = currentCol + colDelta[i];

        if (row >= 0 &&
            row < grid.Length &&
            col >= 0 &&
            col < grid[row].Length &&
            grid[row][col] != -1)
        {
            int key = row * keyMultiplier + col;
            if (!visited.ContainsKey(key))
            {
                visited.Add(key, true);
                ClassicBacktracking(grid, row, col, endRow, endCol, countNonObstacles, visited, keyMultiplier, ref countUniquePaths);
                visited.Remove(key);
            }
        }
    }
}

private void PreprocessGrid(int[][] grid,
                            out int startRow,
                            out int startCol,
                            out int endRow,
                            out int endCol,
                            out int countNonObstacles,
                            out int keyMultiplier)
{
    startRow = -1;
    startCol = -1;
    endRow = -1;
    endCol = -1;
    countNonObstacles = 0;

    keyMultiplier = Math.Max(grid.Length, grid[0].Length) + 1;

    for (int r = 0; r < grid.Length; r++)
    {
        for (int c = 0; c < grid[r].Length; c++)
        {
            if (grid[r][c] == 1)
            {
                startRow = r;
                startCol = c;
            }
            if (grid[r][c] == 2)
            {
                endRow = r;
                endCol = c;
            }
            if (grid[r][c] != -1)
            {
                countNonObstacles++;
            }
        }
    }
}