# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
def getDecimalValue(self, head: ListNode) -> int:
r = 0
r = r * 2 + head.val
return r


class Solution:
def sequentialDigits(self, low: int, high: int) -> List[int]:
ret = []
for s in range(1, 10):
c = s
i = s + 1
while c < high and i < 10:
c = c * 10 + i
i += 1
if low <= c <= high:
ret.append(c)
ret.sort()
return ret


class Solution:
def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
# 预处理，方便查询数组中矩形区域的和
n = len(mat)
m = len(mat[0])
s = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n):
for j in range(m):
s[i][j] = s[i-1][j] + s[i][j-1] + mat[i][j] - s[i-1][j-1]

# 判断是否存在边长为 c 的所有数字之和小于 threshold 的正方形区域
def check(c):
for i in range(n-c+1):
for j in range(m-c+1):
if s[i+c-1][j+c-1] - s[i-1][j+c-1] - s[i+c-1][j-1] + s[i-1][j-1] <= threshold:
return True
return False

# 二分查找
a = 0
b = min(n, m)
r = 0
while a <= b:
c = (a + b) // 2
if check(c):
r = c
a = c + 1
else:
b = c - 1
return r


class Solution:
def shortestPath(self, grid: List[List[int]], k: int) -> int:
n = len(grid)
m = len(grid[0])
ans = [-1]
visited = [[False] * m for _ in range(n)]
def dfs(x, y, s, c):
if ans[0] == (n+m-2) or ans[0] != -1 and ans[0] < s:
return
if x == n-1 and y == m-1:
ans[0] = s
return
for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
cx = x + dx
cy = y + dy
if cx < 0 or cy < 0 or cx >= n or cy >= m or visited[cx][cy]:
continue
visited[cx][cy] = True
if (grid[cx][cy] == 0):
dfs(cx, cy, s+1, c)
elif c > 0:
dfs(cx, cy, s+1, c-1)
visited[cx][cy] = False

visited[0][0] = True
dfs(0, 0, 0, k)
return ans[0]