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()