<p>Given an <code>n x n</code> binary matrix <code>grid</code>, return <em>the length of the shortest <strong>clear path</strong> in the matrix</em>. If there is no clear path, return <code>-1</code>.</p>

<p>A <strong>clear path</strong> in a binary matrix is a path from the <strong>top-left</strong> cell (i.e., <code>(0, 0)</code>) to the <strong>bottom-right</strong> cell (i.e., <code>(n - 1, n - 1)</code>) such that:</p>

<ul>
	<li>All the visited cells of the path are <code>0</code>.</li>
	<li>All the adjacent cells of the path are <strong>8-directionally</strong> connected (i.e., they are different and they share an edge or a corner).</li>
</ul>

<p>The <strong>length of a clear path</strong> is the number of visited cells of this path.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/02/18/example1_1.png" style="width: 500px; height: 234px;" />
<pre>
<strong>Input:</strong> grid = [[0,1],[1,0]]
<strong>Output:</strong> 2
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/02/18/example2_1.png" style="height: 216px; width: 500px;" />
<pre>
<strong>Input:</strong> grid = [[0,0,0],[1,1,0],[1,1,0]]
<strong>Output:</strong> 4
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,0,0],[1,1,0],[1,1,0]]
<strong>Output:</strong> -1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= n &lt;= 100</code></li>
	<li><code>grid[i][j] is 0 or 1</code></li>
</ul>

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        def helper(row, col):
            # Base case: out of bounds or obstacle or already visited
            if row >= rows or col >= cols or row < 0 or col < 0 or grid[row][col] == 1 or (row, col) in seen:
                return float("inf")
            
            # Reached the start (0, 0), so return 1 (since it's a valid step)
            if row == 0 and col == 0:
                return 1

            # Return cached result if already computed
            if (row, col) in hashMap:
                return hashMap[(row, col)]

            # Mark the cell as visited
            seen.add((row, col))
            currPath = float("inf")
            
            # All 8 directions (including diagonals)
            directions = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)]
            
            # Explore all possible directions
            for r, c in directions:
                currPath = min(currPath, helper(row + r, col + c))
            
            # Cache the result for this cell (row, col)
            hashMap[(row, col)] = currPath
            
            # Backtrack (remove from seen)
            seen.remove((row, col))
            
            # If currPath is valid, return it + 1 (for the current step), else return infinity
            return currPath + 1 if currPath != float("inf") else float("inf")

        # Edge case: if the start or end is blocked, return -1
        if grid[0][0] == 1 or grid[-1][-1] == 1:
            return -1

        # Initialize variables
        hashMap = {}
        seen = set()
        rows, cols = len(grid), len(grid[0])

        # Start the helper from the bottom-right corner
        pathCount = helper(rows - 1, cols - 1)

        # If no valid path is found, return -1, else return the path count
        return -1 if pathCount == float("inf") else pathCount



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

        if grid[0][0] == 1:
            return -1
        q = deque([(0,0,1)])
        rows, cols = len(grid), len(grid[0])
        while q:
            row, col, dist = q.popleft()
            if row == rows-1 and col == cols-1:
                return dist

            distance = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)]
            for r,c in distance:
                newRow, newCol = row+r, col+c
                if newRow >= 0 and newRow < rows and newCol >= 0 and newCol < cols and grid[newRow][newCol] == 0:
                    q.append([newRow, newCol, dist+1])
                    grid[newRow][newCol] = 1

        return -1

   
17100