头条推箱子

#!/usr/bin/env python
# -*- coding: utf-8 -*-


#一个位置的上下左右
def asides(pos):
    return [(pos[0]-1,pos[1]),
            (pos[0]+1,pos[1]),
            (pos[0],pos[1]-1),
            (pos[0],pos[1]+1)]

def playerSteps(start, end, valids):
    if end not in valids or start not in valids:
        return -1
    player_valids = valids.copy()
    cur_pos = [start]
    player_valids.remove(start)
    count = 0
    while len(cur_pos)>0:
        next_pos = []
        for player in cur_pos:
            if  player == end:
                return count
            for next in asides(player):
                if next in player_valids:
                    player_valids.remove(next)
                    next_pos.append(next)
        count += 1
        cur_pos = next_pos
    return -1

#给出每一次推箱子之前，箱子与人的位置的全部可能状态。
def player_box_valids(valids):
    result = set()
    for box in valids:
        for player in asides(box):
            if player in valids:
                result.add((player, box))
    return  result

def boxSteps(start, end, player, valids):
    pb_valids = player_box_valids(valids)
    cur_status = [(start,0,player)]
    if (player, start) in pb_valids:
        pb_valids.remove((player, start))
    min_step = -1
    while len(cur_status) > 0:
        next_status = []
        for box, step, player in cur_status:
            if box == end:
                if min_step < 0:
                    min_step = step
                else:
                    min_step = min(step, min_step)
            else:
                if 0 < step < min_step:
                    continue
                for next in asides(box):
                    if (box, next) not in pb_valids:
                        continue
                    #玩家要先移动到目标位置相对当前箱子位置的对面
                    player_next = (box[0]*2-next[0], box[1]*2-next[1])
                    player_valids = valids.copy()
                    player_valids.remove(box)
                    player_step = playerSteps(player, player_next,
                                              player_valids)
                    if  player_step == -1:
                        continue
                    next_status.append((next,step+player_step+1,box))
                    pb_valids.remove((box,next))
        cur_status = next_status
        print('next pos : ', next_status)
    return min_step


def get_input():
    line = input()
    n, m = map(int, line.split())
    maze = []
    valids = set()
    player = None
    box = None
    target = None
    for i in range(n):
        line = input()
        for j in  range(m):
            if line[j] == '.':
                valids.add((i,j))
            elif line[j] == 'S':
                player = (i,j)
                valids.add((i,j))
            elif line[j] == 'E':
                target = (i,j)
                valids.add((i,j))
            elif line[j] == '0':
                box = (i,j)
                valids.add((i,j))
    print('box:', box)
    print('target:', target)
    print('player:', player)
    print('valids:', sorted(valids))
    return box, target, player, valids

def main():
    print('min step : ', boxSteps(*get_input()))
    


if __name__ == '__main__':
    main()