<reponame>ZR-Huang/AlgorithmPractices
'''
This is the solution of the problem of No.167 weekly competition

I think it is the good template of the breadth first search algorithm, 
so archive it in this fold.

1293. Shortest Path in a Grid with Obstacles Elimination
Link: https://leetcode-cn.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/
'''

from collections import deque
class Solution:
    def shortestPath(self, grid, k: int) -> int:
        m, n = len(grid), len(grid[0])
        step = 0 
        direct = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        q = deque()
        visited = set()
        q.append((0, 0, k))
        visited.add((0, 0, k))

        # Breadth First Search
        while(q):
            size = len(q)
            for _ in range(size):
                i, j, k = q.popleft()
                # visited.add((i,j,k))
                if i == m-1 and j == n-1:
                    return step
                
                for di, dj in direct:
                    ni, nj = i+di, j+dj
                    if ni < 0 or nj < 0 or ni > m-1 or nj > n-1 or (grid[ni][nj]==1 and k<=0):
                        continue
                    
                    if grid[ni][nj] == 1 and (ni,nj,k-1) not in visited:
                        q.append((ni, nj, k-1))
                        visited.add((ni, nj, k-1))
                    elif grid[ni][nj] == 0 and (ni,nj,k) not in visited:
                        q.append((ni, nj, k))
                        visited.add((ni, nj, k))
            step += 1
        
        return -1

grid = [[0,0,1,0,0,0,0,1,0,1,1,0,0,1,1],[0,0,0,1,1,0,0,1,1,0,1,0,0,0,1],[1,1,0,0,0,0,0,1,0,1,0,0,1,0,0],[1,0,1,1,1,1,0,0,1,1,0,1,0,0,1],[1,0,0,0,1,1,0,1,1,0,0,1,1,1,1],[0,0,0,1,1,1,0,1,1,0,0,1,1,1,1],[0,0,0,1,0,1,0,0,0,0,1,1,0,1,1],[1,0,0,1,1,1,1,1,1,0,0,0,1,1,0],[0,0,1,0,0,1,1,1,1,1,0,1,0,0,0],[0,0,0,1,1,0,0,1,1,1,1,1,1,0,0],[0,0,0,0,1,1,1,0,0,1,1,1,0,1,0]]
k = 27
print(Solution().shortestPath(grid, k))
'''
This is the solution of the problem of No.167 weekly competition

I think it is the good template of the breadth first search algorithm, 
so archive it in this fold.

1293. Shortest Path in a Grid with Obstacles Elimination
Link: https://leetcode-cn.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/
'''

from collections import deque
class Solution:
    def shortestPath(self, grid, k: int) -> int:
        m, n = len(grid), len(grid[0])
        step = 0 
        direct = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        q = deque()
        visited = set()
        q.append((0, 0, k))
        visited.add((0, 0, k))

        # Breadth First Search
        while(q):
            size = len(q)
            for _ in range(size):
                i, j, k = q.popleft()
                # visited.add((i,j,k))
                if i == m-1 and j == n-1:
                    return step
                
                for di, dj in direct:
                    ni, nj = i+di, j+dj
                    if ni < 0 or nj < 0 or ni > m-1 or nj > n-1 or (grid[ni][nj]==1 and k<=0):
                        continue
                    
                    if grid[ni][nj] == 1 and (ni,nj,k-1) not in visited:
                        q.append((ni, nj, k-1))
                        visited.add((ni, nj, k-1))
                    elif grid[ni][nj] == 0 and (ni,nj,k) not in visited:
                        q.append((ni, nj, k))
                        visited.add((ni, nj, k))
            step += 1
        
        return -1

grid = [[0,0,1,0,0,0,0,1,0,1,1,0,0,1,1],[0,0,0,1,1,0,0,1,1,0,1,0,0,0,1],[1,1,0,0,0,0,0,1,0,1,0,0,1,0,0],[1,0,1,1,1,1,0,0,1,1,0,1,0,0,1],[1,0,0,0,1,1,0,1,1,0,0,1,1,1,1],[0,0,0,1,1,1,0,1,1,0,0,1,1,1,1],[0,0,0,1,0,1,0,0,0,0,1,1,0,1,1],[1,0,0,1,1,1,1,1,1,0,0,0,1,1,0],[0,0,1,0,0,1,1,1,1,1,0,1,0,0,0],[0,0,0,1,1,0,0,1,1,1,1,1,1,0,0],[0,0,0,0,1,1,1,0,0,1,1,1,0,1,0]]
k = 27
print(Solution().shortestPath(grid, k))
This is the solution of the problem of No.167 weekly competition  I think it is the good template of the breadth first search algorithm,  so archive it in this fold.  1293. Shortest Path in a Grid with Obstacles Elimination Link: https://leetcode-cn.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/ # Breadth First Search # visited.add((i,j,k))