#!/usr/bin/env python
# -*-coding:utf-8-*-
# File Name     : f.py
# Description   :
# Author        :
# Creation Date : 2021-11-01
# Last Modified : 2021年11月01日 星期一 07时14分09秒
# Created By    : lsl

import collections


def f(grid,k):
    m,n = len(grid), len(grid[0])
    seen = set({(0,0,k)})
    queue = collections.deque([(0,0,k)])
    k = min(k, m + n-3)
    step = 0
    while queue:
        size = len(queue)
        for _ in range(size):
            x,y,k = queue.popleft()
            if x == m - 1 and y == n - 1:
                return step
            for nx,ny in [(0,1), (0,-1), (1,0), (-1,0)]:
                x1 = x + nx
                y1 = y + ny
                item = (x1, y1, k)
                if 0 <= x1 < m and 0 <= y1 < n:
                    if grid[x1][y1] == 0:
                        if item not in seen:
                            queue.append((x1, y1, k))
                            seen.add(item)
                    else:
                        if k > 0:
                            if item not in seen:
                                queue.append((x1, y1, k-1))
                                seen.add(item)
        step += 1


    return -1


grid = [[0,0,0],
 [1,1,0],
 [0,0,0],
 [0,1,1],
 [0,0,0]]
k = 1
print(f(grid, k))
print(f([[0]],1))
