PAST3G

PAST3G

G

障害物のあるグリッドの上を将棋の金将がスタートからゴールまで移動するときの最短経路長を求める問題。

幅優先探索。障害物が置かれうる範囲の外側1マス用意すれば迂回経路には十分。

バグりやすそうなのでまずグリッドのサイズを5x5にしたバージョンでデバッグ出力しながらバグを潰した。

初回提出は訪問済みのマスに印をつけ忘れてタイムリミット超過。小さいデータでテストしてた時は気づかなかった。

2回目提出はランタイムエラー、グリッドサイズを1マス少なく計算してた。-1から1の範囲にマス目は3つある。

code:python

TINY_TEST = False

if TINY_TEST:

MIN_BOUND = -2

MAX_BOUND = 2

else:

MIN_BOUND = -200

MAX_BOUND = 200

WIDTH = (MAX_BOUND - MIN_BOUND) + 4 # why not 3?

def setMap(p, v):

x, y = p

def getMap(p):

x, y = p

START = (0, 0)

if TINY_TEST:

GOAL = (2, 2)

setMap(START, "S")

setMap(GOAL, "G")

for p in obstacles:

setMap(p, "#")

else:

setMap((X, Y), "G")

for i in range(N):

setMap(p, "#")

def pp(map):

for line in map:

print("".join(line))

def main():

def visit(x, y):

if getMap((x, y)) == "G":

return True

if getMap((x, y)) != ".":

return

if x < MIN_BOUND-1 or MAX_BOUND+1 < x:

return

if y < MIN_BOUND-1 or MAX_BOUND+1 < y:

return

newFront.append((x, y))

setMap((x, y), "v")

for numSteps in range(1, 1000):

front = set(newFront)

# print("len front,", len(front), numSteps)

# print(front)

newFront = []

for x, y in front:

isFinished = (

visit(x + 1, y + 1)

or visit(x, y + 1)

or visit(x - 1, y + 1)

or visit(x + 1, y)

or visit(x - 1, y)

or visit(x, y - 1))

if isFinished:

print(numSteps)

return

if not newFront:

print(-1)

return

main()