Problem:


Score : 400 points

Problem Statement

A maze is composed of a grid of H \times W squares - H vertical, W horizontal.

The square at the i-th row from the top and the j-th column from the left - (i,j) - is a wall if S_{ij} is # and a road if S_{ij} is ..

There is a magician in (C_h,C_w). He can do the following two kinds of moves:

Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.

Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.

In either case, he cannot go out of the maze.

At least how many times does he need to use the magic to reach (D_h, D_w)?

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

S_{C_h C_w} and S_{D_h D_w} are ..

(C_h,C_w) \neq (D_h,D_w)

Input

Input is given from Standard Input in the following format:

H W
C_h C_w
D_h D_w
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}

Output

Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w), print -1 instead.

Sample Input 1

4 4
1 1
4 4
..#.
..#.
.#..
.#..

Sample Output 1

1

For example, by walking to (2,2) and then using the magic to travel to (4,4), just one use of magic is enough.

Note that he cannot walk diagonally.

Sample Input 2

4 4
1 4
4 1
.##.
####
####
.##.

Sample Output 2

-1

He cannot move from there.

Sample Input 3

4 4
2 2
3 3
....
....
....
....

Sample Output 3

0

No use of magic is needed.

Sample Input 4

4 5
1 2
2 5
#.###
####.
#..##
#..##

Sample Output 4

2



Sample input:
4 4
1 1
4 4
..#.
..#.
.#..
.#..


Sample output:
1

Submission status: Runtime Error

Solution code:
import queue
h,w = map(int,input().split())
sy,sx= map(int,input().split())
gy,gx= map(int,input().split())
S=[]



for i in range(h):
    S.append(input())
    
move = [[x,y] for x in range(-2,3) for y in range(-2,3)] 
walk = [[1,0],[-1,0],[0,1],[0,-1]]
dist = [[99999]*w for i in range(h)]
#visited = [[0]*w for i in range(h)]

q=queue.Queue()
q.put((sx-1,sy-1,0))
dist[sy][sx]=0
goaled = 0

#while goaled==0:
while not q.empty():
    
    x,y,d = q.get()
    
    if x==gx-1 and y==gy-1:
        goaled=1
#        print(d)
#        break
    
    print(x,y,d)
    for i in move:
        if 0<=x+i[0]<w and 0<=y+i[1]<h:
            if S[y+i[1]][x+i[0]]!="#" :
            
#                if visited[x+i[0]][y+i[1]] == 0:
                if dist[y+i[1]][x+i[0]] > d:
                
                    

                    if abs(i[0])+abs(i[1])==1:
                        dist[y+i[1]][x+i[0]] = d
                        q.put((x+i[0],y+i[1],d+0))
                    else:  
                        dist[y+i[1]][x+i[0]] = d+1
                        q.put((x+i[0],y+i[1],d+1))

Submission status: Runtime Error

Solution code:
from collections import deque


def bfs(u, n, g):
    queue = deque([u])
    d = [None] * n  # uからの距離の初期化
    d[u] = 0  # 自分との距離は0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
    return d


def main():
    h, w = map(int, input().split())
    c_h, c_w = map(lambda x: int(x) - 1, input().split())
    d_h, d_w = map(lambda x: int(x) - 1, input().split())
    s = [None] * h
    for i in range(h):
        s[i] = input()
    area = [[None] * w for i in range(h)]
    area_cnt = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                continue

            if i > 0 and area[i - 1][j] is not None:
                area[i][j] = area[i - 1][j]
            elif j > 0 and area[i][j - 1] is not None:
                area[i][j] = area[i][j - 1]
            else:
                area[i][j] = area_cnt
                area_cnt += 1

    c_area = area[c_h][c_w]
    d_area = area[d_h][d_w]

    if c_area == d_area:
        print(0)
        return

    can_move = [set([]) for _ in range(area_cnt)]
    for i in range(h):
        for j in range(w):
            if area[i][j] is None:
                continue
            for k in range(-2, 3):
                if i + k < 0 or area_cnt <= i + k:
                    continue
                for m in range(-2, 3):
                    if j + m < 0 or area_cnt <= j + m:
                        continue
                    if area[i + k][j + m] is None:
                        continue
                    try:
                        if area[i][j] != area[i + k][j + m]:
                            can_move[area[i][j]].add(area[i + k][j + m])
                            can_move[area[i + k][j + m]].add(area[i][j])
                    except IndexError:
                        pass
    d = bfs(c_area, area_cnt, can_move)[d_area]
    if d is None:
        print(-1)
    else:
        print(d)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
h,w = map(int, input().split())
hstart, wstart= map(int, input().split())
hend, wend= map(int, input().split())

matrix= []
for i in range(h):
	matrix.append(list(input())+['#','#','#','#','#','#','#','#'])

for i in range(10):
	matrix.append(['#']*(w+8))

matrix[hstart-1][wstart-1]= 0

#print(matrix)
def check_surrounds(h, w):
	if matrix[h][w]!='.' and matrix[h][w]!='#':
		value= matrix[h][w]
		

		if matrix[h+1][w]!='#':
			if matrix[h+1][w] == '.':
				matrix[h+1][w]= value
				check_surrounds(h+1, w)
			elif matrix[h+1][w]>value:
				matrix[h+1][w]= value
				check_surrounds(h+1, w)
		if matrix[h][w+1]!='#':
			if matrix[h][w+1] == '.':
				matrix[h][w+1]= value
				check_surrounds(h, w+1)
			elif matrix[h][w+1] >value:
				matrix[h][w+1]= value
				check_surrounds(h, w+1)
		if matrix[h-1][w]!='#':		
			if matrix[h-1][w] == '.':
				matrix[h-1][w]= value
				check_surrounds(h-1, w)
			elif matrix[h-1][w] > value:
				matrix[h-1][w]= value
				check_surrounds(h-1, w)
		if matrix[h][w-1] != '#':
			if matrix[h][w-1] == '.':
				matrix[h][w-1]= value
				check_surrounds(h, w-1)
			elif matrix[h][w-1] >value:
				matrix[h][w-1]= value
				check_surrounds(h, w-1)
		for i in range(-2, 3):
			for j in range(-2,3):
		#		print(h+i, w+j)
				if matrix[h+i][w+j]!='#':
					if matrix[h+i][w+j]=='.':
						matrix[h+i][w+j]= value+1
						check_surrounds(h+i,w+j)
					elif matrix[h+i][w+j]>value+1:
						matrix[h+i][w+j]= value+1
						check_surrounds(h+i,w+j)
			

check_surrounds(hstart-1, wstart-1)

if matrix[hend-1][wend-1] == '#' or matrix[hend-1][wend-1] == '.':
	print(-1)
else:
	print(matrix[hend-1][wend-1])

Submission status: Runtime Error

Solution code:
from copy import deepcopy

H, W = map(int,input().split())
Ch1, Cw1 = map(int,input().split())
Dh1, Dw1 = map(int,input().split())

Ch = Ch1 -1
Cw = Cw1 -1

Dh = Dh1 - 1
Dw = Dw1 - 1


def finding(a,b): #(a,b)から5マス以内に数字マスがあるか索敵
    if type(T[a][b]) == int:
        return T[a][b]
    else:
        V = []
        for i in range(-5,6):
            for j in range(-(5 - abs(i)), 6 - abs(i)):
                if type(T[min(max(0,a-i), H-1)][min(max(0,b-j),W-1)]) == int:
                    V += [T[min(max(0,a-i), H-1)][min(max(0,b-j),W-1)]]
        if V != []:
            return min(n + 1 for n in V)
        else:
            return T[a,b]
            


i = 0
S = []
while i < H:
    li = list(input().split())
    S += [li]
    i += 1

T = deepcopy(S)
T[Ch][Cw] = 0
U = []
while T!= U:
    while T != U:
        U = deepcopy(T)
        for i in range(H):
            for j in range(W):
                if T[i][j] != '#':
                    if type(T[max(i-1,0)][max(j-1,0)]) == int:
                        T[i][j] = T[max(i-1,0)][max(j-1,0)]
                    if type(T[max(i-1,0)][min(j+1,W-1)]) == int:
                        T[i][j] = T[max(i-1,0)][min(j+1,W-1)]
                    if type(T[min(i+1,H-1)][min(j+1,W-1)]) == int:
                        T[i][j] = T[min(i+1,H-1)][min(j+1,W-1)]
                    if type(T[min(i+1,H-1)][max(j-1,0)]) == int:
                        T[i][j] = T[max(i+1,H-1)][max(j-1,0)]
    for a in range(H):
        for b in range(W):
            if T[a,b] != '#':
                T[a][b] = finding(a,b)


if T[Dh][Dw] == '.':
    print(-1)
else:
    print(T[Dh][Dw])

Submission status: Runtime Error

Solution code:
import collections
import sys
H, W, M = [int(x) for x in input().split()]
h = list()
w = list()
graph = [[0 for _ in range(W)] for _ in range(H)]
for _ in range(M):
  a, b = [int(x) for x in input().split()]
  graph[a-1][b-1] = 1
  h.append(a)
  w.append(b)
h_count = collections.Counter(h)
w_count = collections.Counter(w)
h_max = h_count.most_common()
w_max = w_count.most_common()
h_max_value = h_max[0][1]
w_max_value = w_max[0][1]

h_num = len([i for i in range(len(h_max)) if(h_max_value==h_max[i][1])])
w_num = len([i for i in range(len(w_max)) if(w_max_value==w_max[i][1])])

for i in range(h_num):
  for j in range(w_num):
    if(graph[h_max[i][0]-1][w_max[j][0]-1] == 0):
      ans = (h_max[i][1] + w_max[j][1])
      print(ans)
      sys.exit()

ans = h_max[0][1] + w_max[0][1] -1
print(ans)

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
amap = []
for _ in range(h):
  amap.append([ s for s in input()])
posh = ch - 1
posw = cw - 1
time = 0
ans = 10000
mva = [ (0,1), (1,0), (0,-1), (-1,0) ]
mvb = [ (-2,2), (-1,2), (0,2), (1,2), (2,2), 
        (-2, 1), (-1, 1), (1, 1), (2, 1), 
       (-2, 0), (2, 0),
       (-2, -1), (-1, -1), (1, -1), (2, -1), 
      (-2,-2), (-1,-2), (0,-2), (1,-2), (2,-2),
      ]
def possible(y, x):
  if x<0 or y>=h or y<0 or x>=w:
    return False
  if amap[y][x] == '#':
    return False
  if amap[y][x] == '.':
    return True

def dfs(posh, posw, time):
  global ans
  if posh == (dh-1) and posw == (dw-1):
    if time < ans:
      ans = time
  amap[posh][posw] = '#'
  for y, x in mva:
    if possible(posh+y,posw+x):
      dfs(posh+y, posw+x, time)
  for y, x in mvb:
    if possible(posh+y,posw+x):
      time = time + 1
      dfs(posh+y, posw+x, time)
  
      
dfs(posh, posw, time)
if ans == 10000:
  print(-1)
else:
  print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque


def bfs(u, n, g):
    queue = deque([u])
    d = [None] * n  # uからの距離の初期化
    d[u] = 0  # 自分との距離は0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
    return d


def main():
    h, w = map(int, input().split())
    c_h, c_w = map(lambda x: int(x) - 1, input().split())
    d_h, d_w = map(lambda x: int(x) - 1, input().split())
    s = [None] * h
    for i in range(h):
        s[i] = input()
    area = [[None] * w for i in range(h)]
    area_cnt = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                continue

            if i > 0 and area[i - 1][j] is not None:
                area[i][j] = area[i - 1][j]
            elif j > 0 and area[i][j - 1] is not None:
                area[i][j] = area[i][j - 1]
            else:
                area[i][j] = area_cnt
                area_cnt += 1

    c_area = area[c_h][c_w]
    d_area = area[d_h][d_w]

    if c_area == d_area:
        print(0)
        return

    can_move = [set([]) for _ in range(area_cnt)]
    for i in range(h):
        for j in range(w):
            if area[i][j] is None:
                continue
            for k in range(-2, 3):
                if i + k < 0 or area_cnt <= i + k:
                    continue
                for m in range(-2, 3):
                    
                    if j + m < 0 or area_cnt <= j + m:
                        continue
                    if area[i + k][j + m] is None:
                        continue
                    try:
                        if area[i][j] != area[i + k][j + m]:
                            can_move[area[i][j]].add(area[i + k][j + m])
                            can_move[area[i + k][j + m]].add(area[i][j])
                    except IndexError:
                        pass
    d = bfs(c_area, area_cnt, can_move)[d_area]
    if d is None:
        print(-1)
    else:
        print(d)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
h, w = list(map(int, input().split()))
ch, cw = list(map(int, input().split()))
dh, dw = list(map(int, input().split()))
s = [list(input()) for _ in range(h)]

g = {}

def dump():
    print('map')
    for row in s:
        print(''.join(row))
    print('graph')
    print(g)
    print()

ident = 0
def fill_cluster(x, y, no=None):
    global ident
    if not (0 <= x < h) or not (0 <= y < w):
        return
    if s[x][y] != '.':
        return
    
    if no is None:
        ident += 1
        g[ident] = set()

    s[x][y] = str(ident)

    # 移動A
    fill_cluster(x, y - 1, ident)
    fill_cluster(x, y + 1, ident)
    fill_cluster(x - 1, y, ident)
    fill_cluster(x + 1, y, ident)

fill_cluster(ch - 1, cw - 1)
fill_cluster(dh - 1, dw - 1)
for i in range(h):
    for j in range(w):
        fill_cluster(i, j)
#dump()

def check_cluster_connectivity(x, y, prev=None):
    if not (0 <= x < h) or not (0 <= y < w):
        return
    if s[x][y] == '#':
        return

    curr = s[x][y]
    curr = int(curr)
    if prev is not None and curr != prev:
        # warpできる
        k = int(s[x][y])
        g[prev].add(k)

    _prev = int(s[x][y])

    s[x][y] = '#'

    # 移動B
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            check_cluster_connectivity(x + dx, y + dy, _prev)

for i in range(h):
    for j in range(w):
        check_cluster_connectivity(i, j)

dist = {k:None for k in g}
def bfs(pos, d):
    if dist[pos] is not None:
        return
    dist[pos] = d
    for e in g[pos]:
        bfs(e, d + 1)

if len(g) == 1:
    # スタート = ゴール
    print(0)
elif len(g[1]) == 0:
    # 経路なし
    print(-1)
else:
    # 経路あり ⇒ BfS
    bfs(1, 0)
    print(dist[2])

Submission status: Runtime Error

Solution code:
from collections import deque


def bfs(u, n, g):
    queue = deque([u])
    d = [None] * n  # uからの距離の初期化
    d[u] = 0  # 自分との距離は0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
    return d


def main():
    h, w = map(int, input().split())
    c_h, c_w = map(lambda x: int(x) - 1, input().split())
    d_h, d_w = map(lambda x: int(x) - 1, input().split())
    s = [None] * h
    for i in range(h):
        s[i] = input()
    area = [[None] * w for i in range(h)]
    area_cnt = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                continue

            if i > 0 and area[i - 1][j] is not None:
                area[i][j] = area[i - 1][j]
            elif j > 0 and area[i][j - 1] is not None:
                area[i][j] = area[i][j - 1]
            else:
                area[i][j] = area_cnt
                area_cnt += 1

    c_area = area[c_h][c_w]
    d_area = area[d_h][d_w]

    if c_area == d_area:
        print(0)
        return

    can_move = [set([]) for _ in range(area_cnt)]
    for i in range(h):
        for j in range(w):
            if area[i][j] is None:
                continue
            for k in range(-2, 3):
                if i + k < 0 or area_cnt <= i + k:
                    continue
                for m in range(-2, 3):
                    
                        if j + m < 0 or area_cnt <= j + m:
                            continue
                        if area[i + k][j + m] is None:
                            continue
                    try:
                        if area[i][j] != area[i + k][j + m]:
                            can_move[area[i][j]].add(area[i + k][j + m])
                            can_move[area[i + k][j + m]].add(area[i][j])
                    except IndexError:
                        pass
    d = bfs(c_area, area_cnt, can_move)[d_area]
    if d is None:
        print(-1)
    else:
        print(d)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
H,W,M = map(int,input().split())
T = [0] * M
H_cnt = {}
W_cnt = {}
HW = {}
for i in range(M):
    h,w = map(int,input().split())
    if not h in H_cnt:
        H_cnt[h] = 0
    if not w in W_cnt:
        W_cnt[w] = 0
    H_cnt[h] += 1
    W_cnt[w] += 1
    HW[(h,w)] = 1

HL = [[h,cnt] for h,cnt in H_cnt.items()]
WL = [[w,cnt] for w,cnt in W_cnt.items()]

HL.sort(key=lambda x: x[1],reverse=True)
WL.sort(key=lambda x: x[1],reverse=True)

HS = []
max_cnt = 0
for h,cnt in HL:
    if max_cnt<=cnt:
        HS.append([h,cnt])
        continue
    break

WS = []
max_cnt = 0
for w,cnt in WL:
    if max_cnt<=cnt:
        WS.append([w,cnt])
        continue
    break

cnt = 0
ans = 0
for h,hcnt in HS:
    for w,wcnt in WS:
        if (h,w) in HW:
            cnt = hcnt+wcnt-1
            ans = max(ans,cnt)
            continue
        cnt = hcnt+wcnt
        ans = max(ans,cnt)

print(ans)

Submission status: Runtime Error

Solution code:
h, w = [int(w) for w in input().split()]
ch, cw = [int(w)-1 for w in input().split()]
dh, dw = [int(w)-1 for w in input().split()]

field = [list(input()) for _ in range(h)]
warp = [[1, 1, 1, 1, 1], [1, 1, 0, 1, 1], [
    1, 0, 0, 0, 1], [1, 1, 0, 1, 1], [1, 1, 1, 1, 1]]

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

# N E S W
direction = [[-1, 0], [0, 1], [1, 0], [0, -1]]


def step(_h, _w, _c):
    if _c >= cost[_h][_w]:
        return
    cost[_h][_w] = _c

    # 4
    for d in direction:
        if _h+d[0] < 0 or _h+d[0] >= h or _w+d[1] < 0 or _w+d[1] >= w:
            continue
        if field[_h+d[0]][_w+d[1]] == ".":
            step(_h+d[0], _w+d[1], _c)

    # syuui
    for i in range(-2, 3):
        if _h+i < 0 or _h+i >= h:
            continue
        for j in range(-2, 3):
            if _w+j < 0 or _w+j >= w:
                continue
            if warp[i+2][j+2] == 0:
                continue
            if field[_h+i][_w+j] == ".":
                step(_h+i, _w+j, _c+1)


step(dh, dw, 0)

if cost[ch][cw] == 1e10:
    print(-1)
else:
    print(cost[ch][cw])

Submission status: Runtime Error

Solution code:
import sys
import heapq
INF=10**9
def Dijkstra(graph, start):
  dist={}
  for i in graph:
    dist[i]=INF
  queue=[(0, start)]
  while queue:
    path_len, v=heapq.heappop(queue)
    if dist[v]==INF: 
      dist[v]=path_len
      for w in graph[v]:
        if dist[w]==INF:
          heapq.heappush(queue, (dist[v]+1, w))         
  return dist
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
m=[]
for i in range(h):
  s=input()
  m.append(s)
uf=UnionFind(h*w)
for i in range(h):
  for j in range(w):
    if j+1<w and m[i][j]=='.' and m[i][j+1]=='.':
      uf.union(i+h*j,i+h*(j+1))
    if i+1<h and m[i][j]=='.' and m[i+1][j]=='.':
      uf.union(i+h*j,i+1+h*j)
if uf.same((ch-1)+(cw-1)*h,(dh-1)+(dw-1)*h):
  print(0)
  sys.exit()
graph={}
for i in uf.roots():
  graph[i]=set()
for i in range(h):
  for j in range(w):
    if m[i][j]!='.':
      continue
    for k in range(-2,3):
      for l in range(3):
        if i+k<0 or i+k>=h or j+l>=w:
          continue
        if m[i+k][j+l]!='.' or uf.same(i+k+(j+l)*h,i+j*h):
          continue
        graph[uf.find(i+k+(j+l)*h)].add(uf.find(i+j*h))
        graph[uf.find(i+j*h)].add(uf.find(i+k+(j+l)*h))
dist=Dijkstra(graph,ch-1+(cw-1)*h)
if dist[uf.find(dh-1+(dw-1)*h)]==INF:
  print(-1)
else:
  print(dist[uf.find(dh-1+(dw-1)*h)])

Submission status: Runtime Error

Solution code:
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
d = [input().split() for l in range(a[0])]

gcan = 0
minwarp = 0

import sys
sys.setrecursionlimit(10**7) #再帰関数の呼び出し制限
h,w = a[0],a[1]



def dfs(x,y,z):
    global minwarp
    global gcan
    if not(0 <= x < h) or not(0 <= y < w) or d[x][y] == "#": # 壁に当たったり、探索範囲外になった場合はreturn
        mx = x - 2
        if mx < 0:
            mx = 0
        my = y - 2
        if my < 0:
            my = 0
        px = x + 2
        if px >= h:
            px = h
        py = y + 2
        if py >= w:
            py = w
        for i in range(mx, px):
            for j in range(my, py):
                if d[i][j] == ".":
                    x = i
                    y = j
                    z += 1
                    dfs(x,y,z)
        return
    if x == c[0] and y == c[1]: # ゴールを見つけたら”Yes”を出力して終了
        if minwarp > z:
            minwarp = z
        gcan += 1
        return
        
    d[x][y] = "#" #探索済みを示すためのマーキング
    dfs(x+1,y,z)
    dfs(x-1,y,z)
    dfs(x,y+1,z)
    dfs(x,y-1,z)

sx, sy = b[0], b[1] # スタート位置
sz = 0
dfs(sx, sy, sz)

if gcan == 0:
    print("-1")
else:
    print(str(minwarp))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)
h,w=map(int, input().split())

c1, c2 = map(int, input().split())
d1, d2 = map(int, input().split())

data = []
for i in range(h):data.append(input())

ans = []
for i in range(h):ans.append([1e9]*w)
def solve(nowx, nowy, length):
    if(ans[nowx][nowy] <= length):return 0
    ans[nowx][nowy] = length
    for i in range(5):
        for j in range(5):
            if(i==j):continue
            nextx = nowx+i-2
            nexty = nowy+j-2
            if(nextx < 0 or nextx >= h or nexty < 0 or nexty >= w):continue
            if(data[nextx][nexty] == "."):
                if(abs(i-2)+abs(j-2) <= 1):
                    solve(nextx, nexty, length)
                else:
                    solve(nextx, nexty, length+1)
    return 0
solve(c1-1, c2-1, 0)
if(ans[d1-1][d2-1] == 1e9):print(-1)
else:print(ans[d1-1][d2-1])

Submission status: Runtime Error

Solution code:
def main():
    H,W=map(int,input().split())
    Ch,Cw=map(int,input().split())
    Dh,Dw=map(int,input().split())

    S=[]
    for i in range(H):
        w=list(input())
        S.append(w)

    stack=[]
    S[Ch][Cw]=0
    stack.append([Ch,Cw])
    wall=[]
    counter=0
    while len(stack)>0 and wall>0:
        p=stack.pop()
        ph=p[0]
        pw=p[1]
        #up
        if ph!=H-1:
            ph_next=ph+1
            if S[ph_next][pw]==".":
                S[ph_next][pw]=counter
                stack.append([ph_next][pw])
                if ph_next==Dh and pw==Dw:
                    break
            elif S[ph_next][pw]=="#":
                wall.append([ph_next,pw])
        #down
        if ph!=0:
            ph_next=ph-1
            ph_next = ph + 1
            if S[ph_next][pw] == ".":
                S[ph_next][pw] = counter
                stack.append([ph_next][pw])
                if ph_next==Dh and pw==Dw:
                    break

            elif S[ph_next][pw] == "#":
                wall.append([ph_next,pw])
        #right
        if pw!=W-1:
            pw_next=pw+1
            if S[ph][pw_next]==".":
                S[ph][pw_next]=counter
                stack.append([ph][pw_next])
                if ph==Dh and pw_next==Dw:
                    break
            elif S[ph][pw_next]=="#":
                wall.append([ph,pw_next])
        #left
        if pw!=0:
            pw_next=pw-1
            if S[ph][pw_next]==".":
                S[ph][pw_next]=counter
                stack.append([ph][pw_next])
                if ph==Dh and pw_next==Dw:
                    break
            elif S[ph][pw_next]=="#":
                wall.append([ph,pw_next])

        if len(stack)==0:
            counter+=1
            while len(wall)>0:
                wall_=wall.pop()
                wh=wall_[0]
                ww=wall_[1]
                #leftup
                if ww!=0 and wh!=H-1:
                    if S[wh+1][ww-1]=="#":
                        S[wh + 1][ww - 1]="."
                #up
                if wh!=H-1:
                    if S[wh+1][ww]=="#":
                        S[wh+1][ww]="."
                #rightup
                if ww!=W-1 and wh!=H-1:
                    if S[wh+1][ww+1]=="#":
                        S[wh+1][ww+1]="."
                #left
                if ww!=0:
                    if S[wh][ww-1]=="#":
                        S[wh][ww-1]="."
                #right
                if ww!=W-1:
                    if S[wh][ww+1]=="#":
                        S[wh][ww+1]="."
                #leftdown
                if ww!=0 and wh!=0:
                    if S[wh-1][ww-1]=="#":
                        S[wh-1][ww-1]="."
                #down
                if wh!=0:
                    if S[wh-1][ww]=="#":
                        S[wh-1][ww]="."
                #rightdown
                if wh!=0 and ww!=W-1:
                    if S[wh-1][ww+1]=="#":
                        S[wh-1][ww+1]="."

                stack.append(wall_)

    print(counter)

if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
d = [input().split() for l in range(a[0])]

gcan = 0
minwarp = 0

import sys
sys.setrecursionlimit(10**7) #再帰関数の呼び出し制限
h,w = a[0],a[1]



def dfs(x,y,z):
    global minwarp
    global gcan
    if not(0 <= x < h) or not(0 <= y < w) or c[x][y] == "#": # 壁に当たったり、探索範囲外になった場合はreturn
        mx = x - 2
        if mx < 0:
            mx = 0
        my = y - 2
        if my < 0:
            my = 0
        px = x + 2
        if px >= h:
            px = h
        py = y + 2
        if py >= w:
            py = w
        for i in range(mx, px):
            for j in range(my, py):
                if d[i][j] == ".":
                    x = i
                    y = j
                    z += 1
                    dfs(x,y,z)
        return
    if x == c[0] and y == c[1]: # ゴールを見つけたら”Yes”を出力して終了
        if minwarp > z:
            minwarp = z
        gcan += 1
        return
        
    d[x][y] = "#" #探索済みを示すためのマーキング
    dfs(x+1,y,z)
    dfs(x-1,y,z)
    dfs(x,y+1,z)
    dfs(x,y-1,z)

sx, sy = b[0], b[1] # スタート位置
sz = 0
dfs(sx, sy, sz)

if gcan == 0:
    print("-1")
else:
    print(str(minwarp))

Submission status: Runtime Error

Solution code:
def ispossible(i,j):
    if i<0 or j<0 or i>=n or j>=m or a[i][j]=='#':
        return False
    return True
def func(i,j):
    if i<0 or j<0 or i>=n or j>=m or v[i][j]==1:
        return
    v[i][j]=1
    for k1 in range(-1,2):
        for k2 in range(-1,2):
            if(ispossible(i+k1,j+k2)):
                dp[i+k1][j+k2]=min(dp[i+k1][j+k2],dp[i][j])
                if(v[i+k1][j+k2]==0):
                    func(i+k1,j+k2)
    for k1 in range(-2,3):
        for k2 in range(-2,3):
            if(ispossible(i+k1,j+k2)):
                dp[i+k1][j+k2]=min(dp[i+k1][j+k2],dp[i][j]+1)
                if(v[i+k1][j+k2]==0):
                    func(i+k1,j+k2)
    
n,m=[int(i) for i in raw_input().split()]
x1,y1=[int(i)-1 for i in raw_input().split()]
x2,y2=[int(i)-1 for i in raw_input().split()]
dp=[[10**18 for i in range(m)]for j in range(n)]
a=[[i for i in raw_input()]for j in range(n)]
v=[[0 for i in range(m)]for j in range(n)]
dp[x1][y1]=0
func(x1,y1)
if(dp[x2][y2]==10**18):
    print -1
else:
    print dp[x2][y2]

Submission status: Runtime Error

Solution code:

from collections import deque

N,M=map(int,input().split())
starty,startx=map(int,input().split())
goaly,goalx=map(int,input().split())
startx-=1
starty-=1
goalx-=1
goaly-=1


S = [["" for j in range(M)] for i in range(N)]#2行3列の場合
#iがyｊがx






for i in range(N):
    tmp=input()
    for j in range(M):
        S[i][j]=tmp[j]

if N==1 and M==1:
    if S[0,0]=="#":
        print(-1)
    else:
        print(0)




seen=[[-1 for j in range(M)] for i in range(N)]
#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合


dx=[1,0,-1,0]
dy=[0,1,0,-1]
ddx=[2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
ddy=[2,1,0,-1,-2,2,1,-1,-2,2,-2,2,1,-1,-2,2,1,0,-1,-2]


def dfs(y,x):

    todox=deque()
    todoy=deque()
    seen[y][x]=0
    todox.append(x)
    todoy.append(y)
    count=0
    while len(todox) !=0:
        x=todox.popleft()
        y=todoy.popleft()
        count+=1
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx>=0 and nx<M and ny>=0 and ny<N :
                if nx==goalx and ny==goaly:
                    seen[ny][nx]=seen[y][x]
                    #print(seen)
                    return seen[ny][nx]
                        
                if S[ny][nx]==".":
                    
                    
                    
                    if seen[ny][nx] ==-1:
                        #print("mohu",nx,ny)
                        seen[ny][nx] =seen[y][x]
                        todox.append(nx)
                        todoy.append(ny)
                    elif seen[ny][nx] >seen[y][x]:
                        seen[ny][nx] =seen[y][x]
                        todox.append(nx)
                        todoy.append(ny)
                        
        for i in range(20):
            nx=x+ddx[i]
            ny=y+ddy[i]
            if nx>=0 and nx<M and ny>=0 and ny<N :
                
                    
                        
                if S[ny][nx]==".":
                    
                    
                    
                    if seen[ny][nx] ==-1:
                        #print("mohu",nx,ny)
                        seen[ny][nx] =seen[y][x]+1
                        todox.append(nx)
                        todoy.append(ny)
    

            
    return seen[ny][nx]

            
print(dfs(starty,startx))

Submission status: Runtime Error

Solution code:
def ispossible(i,j):
    if i<0 or j<0 or i>=n or j>=m or a[i][j]=='#':
        return False
    return True
def func(i,j):
    if i<0 or j<0 or i==n or j==m or v[i][j]==1:
        return
    v[i][j]=1
    for k1 in range(-1,2):
        for k2 in range(-1,2):
            if(ispossible(i+k1,j+k2)):
                dp[i+k1][j+k2]=min(dp[i+k1][j+k2],dp[i][j])
                if(v[i+k1][j+k2]==0):
                    func(i+k1,j+k2)
    for k1 in range(-2,3):
        for k2 in range(-2,3):
            if(ispossible(i+k1,j+k2)):
                dp[i+k1][j+k2]=min(dp[i+k1][j+k2],dp[i][j]+1)
                if(v[i+k1][j+k2]==0):
                    func(i+k1,j+k2)
    
n,m=[int(i) for i in raw_input().split()]
x1,y1=[int(i)-1 for i in raw_input().split()]
x2,y2=[int(i)-1 for i in raw_input().split()]
dp=[[10**18 for i in range(m)]for j in range(n)]
a=[[i for i in raw_input()]for j in range(n)]
v=[[0 for i in range(m)]for j in range(n)]
dp[x1][y1]=0
func(x1,y1)
if(dp[x2][y2]==10**18):
    print -1
else:
    print dp[x2][y2]