목차

레이저 통신

ps
링크acmicpc.net/…
출처BOJ
문제 번호6087
문제명레이저 통신
레벨골드 3
분류

0-1 BFS

시간복잡도O(nm)
인풋사이즈n<=100, m<=100
사용한 언어Python
제출기록37420KB / 236ms
최고기록64ms
해결날짜2022/09/22

풀이

코드

"""Solution code for "BOJ 6087. 레이저 통신".

- Problem link: https://www.acmicpc.net/problem/6087
- Solution link: http://www.teferi.net/ps/problems/boj/6087

Tags: [0-1 BFS]
"""

import functools
from teflib import graph as tgraph
from teflib import search

COW = 'C'
WALL = '*'
INF = float('inf')


def next_states(state, graph, walls):
    u, cur_dir = state
    for v in graph[u]:
        if v not in walls:
            next_dir = v - u
            w = 0 if cur_dir == next_dir else 1
            yield ((v, next_dir), w)


def main():
    W, H = [int(x) for x in input().split()]
    grid = ''.join(input() for _ in range(H))

    source = grid.index(COW)
    dest = grid.index(COW, source + 1)
    sources = [(source, d) for d in (-W, 1, W, -1)]
    walls = {u for u, x in enumerate(grid) if x == WALL}
    dists = search.zero_one_distances(
        functools.partial(next_states,
                          graph=tgraph.GridGraph(H, W),
                          walls=walls), sources)
    answer = min(dists.get((dest, d), INF) for d in (-W, 1, W, -1))
    print(answer)


if __name__ == '__main__':
    main()