ARC005 C - 器物損壊！高橋君

https://atcoder.jp/contests/arc005/tasks/arc005_3

提出

code: python

from collections import deque

import itertools

h, w = map(int, input().split())

grid = input() for _ in range(h)

# 2回壊すを全探索？

# print(2500*2499//2) 3123750

for i in itertools.combinations(, 2)

解答

code: python

from collections import deque

h, w = map(int,input().split())

c = list(input()) for _ in range(h)

for i in range(h):

for j in range(w):

if cij == "s":

s = i, j

if cij == "g":

g = i, j

INF = int(1e9)

# costij はマス (i, j) への最短路長

cost = [INF * w for _ in range(h)]

que = deque()

que.append(s)

cost[s0][s1] = 0

while que:

nowi, nowj = que.popleft()

if nowi == g0 and nowj == g1:

break

for i, j in 0, 1], 0, -1, 1, 0, [-1, 0:

nexti, nextj = nowi + i, nowj + j

if nexti < 0 or nexti > h - 1 or nextj < 0 or nextj > w - 1:

continue

# 01-BFS

# 移動先が壁で未到達ならqueの後ろにpush

if cnextinextj == "#" and costnextinextj == INF:

costnextinextj = costnowinowj + 1

que.append(nexti, nextj)

# 移動先が壁でなく未到達ならqueの先頭にpush

if cnextinextj != "#" and costnextinextj == INF:

costnextinextj = costnowinowj

que.appendleft(nexti, nextj)

if cost[g0][g1] <= 2:

print("YES")

else:

print("NO")

テーマ

#bfs

蟻本 2-1 迷路の最短路

メモ

AtCoder ARC 005 C - 器物損壊！高橋君 (試験管水色)

提出

code: python

from collections import deque

h, w = map(int, input().split())

c = list(input()) for _ in range(h)

for i in range(h):

for j in range(w):

if cij == "s":

s = i, j

elif cij == "g":

g = i, j

que = deque(s)

dis = [0 * w for _ in range(h)]

dis[s0][s1] = 1

while que:

nowi, nowj = que.popleft()

for i, j in 0, 1], 0, -1, 1, 0, [-1, 0:

nexti, nextj = nowi + i, nowj + j

if nexti < 0 or nexti > h-1 or nextj < 0 or nextj > w-1 or disnextinextj != 0 or cnextinextj == "#":

continue

else:

disnextinextj = disnowinowj + 1

que.append(nexti, nextj)

if dis[g0][g1]:

print("YES")

else:

# 全通り試す？