KOREATECH 1046: 빠른 길 찾기

Link : judge.koreatech.ac.kr/problem.php?id=1046

---

Python

from sys import stdin
import queue
 
data = []
 
 
def able_move(x, y):
    if x < 0 or y < 0:
        return False
    if x >= map_x or y >= map_y:
        return False
    if map_data[y][x] == '-' or map_data[y][x] == 'E' or map_data[y][x] == 'S':
        return True
    else:
        return False
 
 
def BFS(p_x, p_y):
    que = queue.Queue()
    que.put((p_x, p_y, 0))
 
    while que.qsize():
        p_x, p_y, p_d = que.get()
        if able_move(p_x, p_y):
            if map_data[p_y][p_x] == 'E':
                return p_d
            map_data[p_y][p_x] = '@'
 
            if able_move(p_x + 1, p_y):
                que.put((p_x + 1, p_y, p_d + 1))  # right
            if able_move(p_x - 1, p_y):
                que.put((p_x - 1, p_y, p_d + 1))  # left
            if able_move(p_x, p_y + 1):
                que.put((p_x, p_y + 1, p_d + 1))  # down
            if able_move(p_x, p_y - 1):
                que.put((p_x, p_y - 1, p_d + 1))  # up
    return -1
 
 
testcase = int(stdin.readline().strip())
 
while testcase:
    map_y, map_x = list(map(int, stdin.readline().strip().split(' ')))
    map_data = [[s for s in stdin.readline().strip()] for i in range(map_y)]
    start = (0, 0)
    for t_y, i in enumerate(map_data):
        for t_x, j in enumerate(i):
            if j == 'S':
                start = (t_x, t_y)
 
    print(BFS(start[0], start[1]))
    testcase -= 1
 

FeedBack

1.  

---

 

 

 

cjw.git@gmail.com