VXU1230

if __name__ == "__main__":
    print("\nBFS")
    print("\nshortest depth: ", bfs())
    print("\nDFS")
    print("\nshortest depth: ", dfs())
    print("\nIDDFS", end="")
    print("\nshortest depth: ", iddfs())

VXU1230

def iddfs():
    root = get_root()
    res = float("inf")

    def iddfs_search(node, depth, limit):
        if depth <= limit and node is not None:
            val = node.val
            if val >= 10:
                nonlocal res
                res = min(res, depth)

VXU1230

def dfs():
    root = get_root()
    res = float("inf")

    def dfs_search(node, depth):
        if node is not None:
            val = node.val
            if val >= 10:
                nonlocal res
                res = min(res, depth)

VXU1230

def bfs():
    root = get_root()
    queue = collections.deque()
    queue.appendleft((root, 0))
    res = -1

    while queue:
        node, depth = queue.pop()
        if node.val >= 10:
            res = depth

VXU1230

class Node:
    def __init__(self, val=None):
        self.val = val
        self.left = None
        self.right = None


def get_root():
    values = iter([1, 6, 4, 7, None, None, 9, 8, None, None,
              10, None, None, 5, None, None, 2, 3, None, None, 11, None, None])

VXU1230

def path_search(row_len, col_len):
    dp = [[0 for _ in range(col_len)] for _ in range(row_len)]
    for r in reversed(range(row_len)):
        for c in reversed(range(col_len)):
            if r == row_len-1 and c == col_len-1:
                dp[r][c] = 1
            else:
                if r+1 < row_len:
                    dp[r][c] += dp[r+1][c]
                if c+1 < col_len:

VXU1230

import heapq

def dijkstra(grid):
    seen = set()
    heap = []
    dist = grid[0][0]
    heapq.heappush(heap, (dist, 0, 0))
    row_len = len(grid)
    col_len = len(grid[0])
    min_dist = float('inf')

VXU1230

def a_star(grid):
    def get_heuristic(current, target):
        return max(abs(current[0] - target[0]), abs(current[1] - target[1]))

    if grid[0][0] == 1 or grid[-1][-1] == 1:
        return -1

    n = len(grid)
    target = (n - 1, n - 1)
    heap = []

VXU1230

def get_nei(x, y):
    return [(x + 1, y), (x - 1, y), (x + 1, y - 1), (x - 1, y - 1), (x + 1, y + 1), (x - 1, y + 1), (x, y + 1),
            (x, y - 1)]

VXU1230

def dijkstra(grid):
    if grid[0][0] == 1 or grid[-1][-1] == 1:
        return -1
    n = len(grid)
    heap = []

    seen = set()
    heapq.heappush(heap, (1, 1, 0, 0))
    cache = {(0, 0): 1}
    while heap: