백준
백준 1194 달이 차오른다, 가자. (파이썬)
chldkato
2020. 2. 20. 01:21
https://www.acmicpc.net/problem/1194
1194번: 달이 차오른다, 가자.
첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 영식이가 열쇠를 숨겨놓는 다면 문에 대응하는 열쇠가 없을 수도 있다. 0은 한 개, 1은 적어도 한 개 있다. 그리고, 열쇠는 여러 번 사용할 수 있다.
www.acmicpc.net
bfs로 이동한 것을 표시할 배열을 [x][y][key] 3차원으로 해서 열쇠를 2진법으로 연산하여 조건에 맞게 이동
1. 열쇠가 6개므로 2진법으로 (0~111111)까지 표현가능하므로 열쇠에 해당하는 차수를 64로 설정
2. 이동 중에 소문자를 만나면 or 연산으로 열쇠 보유를 갱신하여 큐에 입력
3. 대문자를 만나면 and 연산으로 알맞은 열쇠를 보유했는지 체크 후 이동
4. 1을 만나면 이동 경로를 출력
from collections import deque
import sys
input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
def bfs(x, y):
q.append([x, y, 0])
c[x][y][0] = 1
while q:
x, y, z = q.popleft()
if a[x][y] == '1':
print(c[x][y][z] - 1)
return
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
if a[nx][ny] != '#' and c[nx][ny][z] == 0:
if a[nx][ny].islower():
nz = z | (1 << (ord(a[nx][ny]) - ord('a')))
if c[nx][ny][nz] == 0:
c[nx][ny][nz] = c[x][y][z] + 1
q.append([nx, ny, nz])
elif a[nx][ny].isupper():
if z & (1 << (ord(a[nx][ny]) - ord('A'))):
c[nx][ny][z] = c[x][y][z] + 1
q.append([nx, ny, z])
else:
c[nx][ny][z] = c[x][y][z] + 1
q.append([nx, ny, z])
print(-1)
n, m = map(int, input().split())
a = [list(input().strip()) for _ in range(n)]
c = [[[0]*64 for _ in range(m)] for _ in range(n)]
q = deque()
for i in range(n):
for j in range(m):
if a[i][j] == '0':
bfs(i, j)