プログラマブロックを移動するにはpythonを使用します
問題の説明
ロボット開発者の武智さんは、1ヶ月後に迫っているカカ杯ロボットコンテストで出品されるロボットを準備しています.準備中のロボットは2 x 1サイズのロボットで、プログラミングによって2 x 1サイズのロボットを0と1からなるN x Nサイズの地図から(N,N)位置に移動しようとしています.オートマトンが移動する地図は左上隅の座標(1,1)で表され、地図内の数字0はスペース1の壁を表す.ロボットは壁のあるセルや地図の外に移動できません.ロボットは座標(1、1)の位置から始め、水平方向に移動し、下図のように前後を区別しません.
オートマチックが移動すると、現在の配置状態が維持されます.たとえば、上の図で1つのセル(1,2)、(1,3)を右に移動すると、2つのセル(2,1)、(2,2)が占有されます.ロボットが占有する2つの格子のいずれも(N,N)位置に到達できる.
オートマチックは以下の条件で回転できます.
上の図に示すように、オートマチックは90度回転できます.ただし、ロボットが占有する2つのセルのうち、いずれも軸であってもよいが、回転方向(軸のセルに対して対角線方向)には壁がない必要がある.ロボットが1マスを移動したり90度回転したりするのに要する時間は正確に1秒です.
0と1で構成された地図指示板が与えられた場合、ロボットを(N,N)位置に移動するのに要する最小時間に戻すための解関数を完了してください.
せいげんじょうけん
boardのエッジ長は5または100以下です.
boardの要素は0または1です.
オートマチックが最初に配置したセル(1、1)、(1、2)は常にゼロです.
入力は、自動機が常に目的地に到達できる場合にのみ与えられます.
ロボットのすべての移動についてBFSを使用します.
ロボットの移動、回転をキューに入れ、n、nに到達したら戻り距離を戻して終了します.
ただし、位置座標が2つあるので、p 1、p 2=p 2、p 1、p 2=p 2、p 1 p 1、p 2=p 2、p 1を扱うために、アクセス時に(p 1、p 2)(p 1、p 2)setを使用した.
hashableアクセスも参照できます.
ロボット開発者の武智さんは、1ヶ月後に迫っているカカ杯ロボットコンテストで出品されるロボットを準備しています.準備中のロボットは2 x 1サイズのロボットで、プログラミングによって2 x 1サイズのロボットを0と1からなるN x Nサイズの地図から(N,N)位置に移動しようとしています.オートマトンが移動する地図は左上隅の座標(1,1)で表され、地図内の数字0はスペース1の壁を表す.ロボットは壁のあるセルや地図の外に移動できません.ロボットは座標(1、1)の位置から始め、水平方向に移動し、下図のように前後を区別しません.
オートマチックが移動すると、現在の配置状態が維持されます.たとえば、上の図で1つのセル(1,2)、(1,3)を右に移動すると、2つのセル(2,1)、(2,2)が占有されます.ロボットが占有する2つの格子のいずれも(N,N)位置に到達できる.
オートマチックは以下の条件で回転できます.
上の図に示すように、オートマチックは90度回転できます.ただし、ロボットが占有する2つのセルのうち、いずれも軸であってもよいが、回転方向(軸のセルに対して対角線方向)には壁がない必要がある.ロボットが1マスを移動したり90度回転したりするのに要する時間は正確に1秒です.
0と1で構成された地図指示板が与えられた場合、ロボットを(N,N)位置に移動するのに要する最小時間に戻すための解関数を完了してください.
せいげんじょうけん
boardのエッジ長は5または100以下です.
boardの要素は0または1です.
オートマチックが最初に配置したセル(1、1)、(1、2)は常にゼロです.
入力は、自動機が常に目的地に到達できる場合にのみ与えられます.
ロボットのすべての移動についてBFSを使用します.
ロボットの移動、回転をキューに入れ、n、nに到達したら戻り距離を戻して終了します.
ただし、位置座標が2つあるので、p 1、p 2=p 2、p 1、p 2=p 2、p 1 p 1、p 2=p 2、p 1を扱うために、アクセス時に(p 1、p 2)(p 1、p 2)setを使用した.
hashableアクセスも参照できます.
from collections import deque
def getNewPos(pos, board):
dir = [[0,1], [1,0], [0,-1], [-1,0]]
newPos = []
y1, x1 = pos[0]
y2, x2 = pos[1]
# 상하좌우 이동
for dy, dx in dir:
if board[y1+dy][x1+dx] == 0 and board[y2+dy][x2+dx] == 0:
newPos.append({(y1+dy, x1+dx), (y2+dy, x2+dx)})
# 가로 -> 세로
if y1 == y2:
for dy, dx in dir[1::2]:
if board[y1+dy][x1+dx] == 0 and board[y2+dy][x2+dx] == 0:
newPos.append({(y1, x1), (y1+dy, x1)})
newPos.append({(y2, x2), (y2+dy, x2)})
# 세로 -> 가로
else:
for dy, dx in dir[::2]:
if board[y1+dy][x1+dx] == 0 and board[y2+dy][x2+dx] == 0:
newPos.append({(y1, x1), (y1, x1+dx)})
newPos.append({(y2, x2), (y2, x2+dx)})
return newPos
def solution(board):
n = len(board)
board = [[1] + b + [1] for b in board]
board = [[1] * (n + 2)] + board + [[1] * (n + 2)]
pos = {(1,1), (1,2)}
q = deque()
visited = []
q.append([pos, 0])
visited.append(pos)
while q:
pos, distance = q.popleft()
distance += 1
for newPos in getNewPos(list(pos), board):
if (n, n) in newPos:
return distance
if newPos not in visited:
q.append([newPos, distance])
visited.append(newPos)
return -1
Reference
この問題について(プログラマブロックを移動するにはpythonを使用します), 我々は、より多くの情報をここで見つけました https://velog.io/@rapsby/프로그래머스-블록-이동하기-pythonテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol