白駿1360号珠子脱出2派SUN
15617 ワード
質問する
インプット
solution import sys
from collections import deque
def bfsr():
global res
visited = [[[[0 for i in range(m)] for i in range(n)] for i in range(m)]
for i in range(n)]
# 4차원 배열을 이용해서 visited를 만들어준다.
while dq:
rx, ry, bx, by, cnt = dq.popleft()
visited[rx][ry][bx][by] = 1
if cnt > 10:
break
for i in range(4):
rnx, rny, cntr = move(rx, ry, dx[i], dy[i]) # 한쪽으로 기울여서 끝까지 보냄
bnx, bny, cntb = move(bx, by, dx[i], dy[i]) # 한쪽으로 기울여서 끝까지 보냄
if board[bnx][bny] == 'O': # 파란공이 먼저 빠지거나 , 같이 빠지면 안되기때문에 먼저 체크를 해준다
continue
elif board[rnx][rny] == 'O': # 파란공이 안바지고 빨간공이 빠지면 성공 출력후 끝
print(cnt)
return
if rnx == bnx and rny == bny: # 이동이 더 많은 것을 뒤로빼줌
if cntr < cntb:
bnx -= dx[i]
bny -= dy[i]
else:
rnx -= dx[i]
rny -= dy[i]
if visited[rnx][rny][bnx][bny] == 0: # 빨간공 , 파란공 위치를 방문한적이 없으면 dq에 삽입해주고 visited를 체크해준다.
visited[rnx][rny][bnx][bny] = 1
dq.append((rnx, rny, bnx, bny, cnt + 1))
print(-1) # 출력을 못했으면 -1 실패
def move(x, y, nx, ny):
cnt = 0
while board[x + nx][y + ny] != '#' and board[x][y] != 'O':
# '#'이 있는곳은 어차피 보드판을 벗어나지 않기때문에 0<=x+nx<n을 체크 안해줘도
# 상관이 없으므로 그냥 '#'이 있는지 현재 O가 있는지 체크만 해주면 끝
# O가 있으면 O위치에서 멈춰서 값을 리턴해준다.
# O가 없고 #을 마주치면 거기서 값을 리턴해준다.
cnt += 1
x += nx
y += ny
return x, y, cnt
input = sys.stdin.readline
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
res = -1
n, m = map(int, input().split())
board = [['' for i in range(m)] for j in range(n)]
dq = deque()
x1, y1, x2, y2 = 0, 0, 0, 0
for i in range(n):
a = input().strip()
for j in range(m):
if a[j] == 'B':
x2 = i
y2 = j
if a[j] == 'R':
x1 = i
y1 = j
board[i][j] = a[j]
dq.append((x1, y1, x2, y2, 1))
bfsr()
説明:
キー(Key)
solution import sys
from collections import deque
def bfsr():
global res
visited = [[[[0 for i in range(m)] for i in range(n)] for i in range(m)]
for i in range(n)]
# 4차원 배열을 이용해서 visited를 만들어준다.
while dq:
rx, ry, bx, by, cnt = dq.popleft()
visited[rx][ry][bx][by] = 1
if cnt > 10:
break
for i in range(4):
rnx, rny, cntr = move(rx, ry, dx[i], dy[i]) # 한쪽으로 기울여서 끝까지 보냄
bnx, bny, cntb = move(bx, by, dx[i], dy[i]) # 한쪽으로 기울여서 끝까지 보냄
if board[bnx][bny] == 'O': # 파란공이 먼저 빠지거나 , 같이 빠지면 안되기때문에 먼저 체크를 해준다
continue
elif board[rnx][rny] == 'O': # 파란공이 안바지고 빨간공이 빠지면 성공 출력후 끝
print(cnt)
return
if rnx == bnx and rny == bny: # 이동이 더 많은 것을 뒤로빼줌
if cntr < cntb:
bnx -= dx[i]
bny -= dy[i]
else:
rnx -= dx[i]
rny -= dy[i]
if visited[rnx][rny][bnx][bny] == 0: # 빨간공 , 파란공 위치를 방문한적이 없으면 dq에 삽입해주고 visited를 체크해준다.
visited[rnx][rny][bnx][bny] = 1
dq.append((rnx, rny, bnx, bny, cnt + 1))
print(-1) # 출력을 못했으면 -1 실패
def move(x, y, nx, ny):
cnt = 0
while board[x + nx][y + ny] != '#' and board[x][y] != 'O':
# '#'이 있는곳은 어차피 보드판을 벗어나지 않기때문에 0<=x+nx<n을 체크 안해줘도
# 상관이 없으므로 그냥 '#'이 있는지 현재 O가 있는지 체크만 해주면 끝
# O가 있으면 O위치에서 멈춰서 값을 리턴해준다.
# O가 없고 #을 마주치면 거기서 값을 리턴해준다.
cnt += 1
x += nx
y += ny
return x, y, cnt
input = sys.stdin.readline
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
res = -1
n, m = map(int, input().split())
board = [['' for i in range(m)] for j in range(n)]
dq = deque()
x1, y1, x2, y2 = 0, 0, 0, 0
for i in range(n):
a = input().strip()
for j in range(m):
if a[j] == 'B':
x2 = i
y2 = j
if a[j] == 'R':
x1 = i
y1 = j
board[i][j] = a[j]
dq.append((x1, y1, x2, y2, 1))
bfsr()
説明:
キー(Key)
import sys
from collections import deque
def bfsr():
global res
visited = [[[[0 for i in range(m)] for i in range(n)] for i in range(m)]
for i in range(n)]
# 4차원 배열을 이용해서 visited를 만들어준다.
while dq:
rx, ry, bx, by, cnt = dq.popleft()
visited[rx][ry][bx][by] = 1
if cnt > 10:
break
for i in range(4):
rnx, rny, cntr = move(rx, ry, dx[i], dy[i]) # 한쪽으로 기울여서 끝까지 보냄
bnx, bny, cntb = move(bx, by, dx[i], dy[i]) # 한쪽으로 기울여서 끝까지 보냄
if board[bnx][bny] == 'O': # 파란공이 먼저 빠지거나 , 같이 빠지면 안되기때문에 먼저 체크를 해준다
continue
elif board[rnx][rny] == 'O': # 파란공이 안바지고 빨간공이 빠지면 성공 출력후 끝
print(cnt)
return
if rnx == bnx and rny == bny: # 이동이 더 많은 것을 뒤로빼줌
if cntr < cntb:
bnx -= dx[i]
bny -= dy[i]
else:
rnx -= dx[i]
rny -= dy[i]
if visited[rnx][rny][bnx][bny] == 0: # 빨간공 , 파란공 위치를 방문한적이 없으면 dq에 삽입해주고 visited를 체크해준다.
visited[rnx][rny][bnx][bny] = 1
dq.append((rnx, rny, bnx, bny, cnt + 1))
print(-1) # 출력을 못했으면 -1 실패
def move(x, y, nx, ny):
cnt = 0
while board[x + nx][y + ny] != '#' and board[x][y] != 'O':
# '#'이 있는곳은 어차피 보드판을 벗어나지 않기때문에 0<=x+nx<n을 체크 안해줘도
# 상관이 없으므로 그냥 '#'이 있는지 현재 O가 있는지 체크만 해주면 끝
# O가 있으면 O위치에서 멈춰서 값을 리턴해준다.
# O가 없고 #을 마주치면 거기서 값을 리턴해준다.
cnt += 1
x += nx
y += ny
return x, y, cnt
input = sys.stdin.readline
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
res = -1
n, m = map(int, input().split())
board = [['' for i in range(m)] for j in range(n)]
dq = deque()
x1, y1, x2, y2 = 0, 0, 0, 0
for i in range(n):
a = input().strip()
for j in range(m):
if a[j] == 'B':
x2 = i
y2 = j
if a[j] == 'R':
x1 = i
y1 = j
board[i][j] = a[j]
dq.append((x1, y1, x2, y2, 1))
bfsr()
キー(Key)
Reference
この問題について(白駿1360号珠子脱出2派SUN), 我々は、より多くの情報をここで見つけました https://velog.io/@slbin-park/백준-1360번-구슬탈출-2-파이썬テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol