算法1

BFS

双重BFS

时间复杂度

参考文献

python 代码

def minPushBox(self, grid: List[List[str]]) -> int:
    # BFS，Q内存放箱子位置和人的位子，入Q条件，箱子和人都能到该子节点
    Q = []
    visited = []
    row = len(grid)
    column = len(grid[0])
    routeRecoder = []
    def isPlayerCanReach(source,target):
        if [source,target] in routeRecoder:
            return True
        q = []
        seen = []
        q.append(source)
        seen.append(source)
        while q:
            tmp = q.pop(0)
            if tmp == target:
                routeRecoder.append([source,target])
                return True
            for direction in directions:
                i = tmp[0]+direction[0]
                j = tmp[1]+direction[1]
                if i in range(row) and j in range(column) and [i,j] not in seen and (grid[i][j] == "." or grid[i][j] =="T"):
                    q.append([i,j])
                    seen.append([i,j])
        return False
    # find the initial place of box and people
    box = []
    people = []
    times = [[0 for _ in range(column)] for _ in range(row)]
    for i in range(row):
        for j in range(column):
            if grid[i][j] == "B":
                box = [i,j]
            elif grid[i][j] == "S":
                people = [i,j]
    Q.append((box, people, 0))
    visited.append((box,people))
    directions = [[1,0],[-1,0],[0,1],[0,-1]]
    while Q:
        tmp = Q.pop(0)
        box_i = tmp[0][0]
        box_j = tmp[0][1]
        people_i = tmp[1][0]
        people_j = tmp[1][1]
        layer = tmp[2]
        times[box_i][box_j] = layer
        if grid[box_i][box_j] == "T":
            return times[box_i][box_j]
        grid[box_i][box_j] = "B"
        grid[people_i][people_j] = "S"
        print("--------parent--------")
        print(tmp[0], tmp[1])
        for direction in directions:
            x = box_i+direction[0]
            y = box_j+direction[1]
            if x not in range(row) or y not in range(column) or grid[x][y] == "#":
                continue
            z = box_i-direction[0]
            w = box_j-direction[1]
            if z not in range(row) or w not in range(column) or ([x, y], [z, w]) in visited:
                continue
            if grid[z][w] != "#" and isPlayerCanReach(tmp[1],[z,w]):
                Q.append(([x,y],[box_i,box_j], layer+1))
                visited.append(([x,y],[box_i,box_j]))
                print("-----------son-------------")
                print(visited[-1])
                # times[x][y] += 1
        grid[box_i][box_j] = "."
        grid[people_i][people_j] = "."
    return -1