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: Time Limit Exceeded

Solution code:
from collections import deque

queue = deque()

H,W = [int(v) for v in input().split()]
ch,cw = [int(v) for v in input().split()]
dh,dw = [int(v) for v in input().split()]

S = [input() for _ in range(H)]
visited = [[-1 for _ in range (W)] for _ in range(H)]

queue.append((cw-1,ch-1,0))

def check(x,y):
    return x > -1 and x < W and y > -1 and y < H and S[y][x] != "#" and visited[y][x] == -1

while len(queue) != 0:
    x,y,c = queue.popleft()
    if visited[y][x] != -1:
        continue
    visited[y][x] = c

    for d in [1,-1]:
        if check(x+d,y):
            queue.appendleft([x+d,y,c])
        if check(x,y+d):
            queue.appendleft([x,y+d,c])
    
    for dx in [-2,-1,0,1,2]:
        for dy in [-2,-1,0,1,2]:
            if check(x+dx,y+dy):
                queue.append((x+dx,y+dy,c+1))

print(visited[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readints():return list(map(int,readline().split()))

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

dist = [10**10]*(h*w)

a = [[]for i in range(2)]
i = 0
a[i].append(start)
dist[start] = 0

while a[0] or a[1]:
    p = a[i].pop()
    y = p//w
    x = p%w
    for dy in range(-2,3):
        for dx in range(-2,3):
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                q = (y+dy)*w + x+dx
                if dist[q]<=dist[p]:
                    continue
                if abs(dy)+abs(dx)==1:
                    a[i].append(q)
                    dist[q] = dist[p]
                else:
                    a[i-1].append(q)
                    dist[q] = dist[p] + 1
    if not a[i]:
        i = [1,0][i]

print(-1 if dist[goal]==10**10 else dist[goal])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    H, W = map(int, readline().split())
    sh, sw = map(int, readline().split())
    gh, gw = map(int, readline().split())
    sh -= 1
    sw -= 1
    gh -= 1
    gw -= 1
    S = read().split()

    dist = [[INF] * W for _ in range(H)]
    walk = ((1, 0), (-1, 0), (0, 1), (0, -1))
    warp = ((-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 1), (-1, 2),
            (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2))

    Q = deque()
    Q.append((sh, sw))
    Q2 = deque()
    dist[sh][sw] = 0

    bl = True

    while bl:
        while Q:
            h, w = Q.popleft()
            if h==gh and w == gw:
                bl = False
                break
            d = dist[h][w]
            flag = 0
            for dh, dw in walk:
                nh = h + dh
                nw = w + dw
                if 0<=nh<H and 0<=nw<W:
                    if S[nh][nw] == '.':
                        if dist[nh][nw] > d:
                            dist[nh][nw] = d
                            Q.append((nh,nw))
                    else:
                        flag += 1
            if flag:
                Q2.append((h,w))
        if bl==False:
            break
        while Q2:
            h, w = Q2.popleft()
            d = dist[h][w]
            for dh, dw in warp:
                nh = h + dh
                nw = w + dw
                if 0<=nh<H and 0<=nw<W:
                    if S[nh][nw] == '.' and dist[nh][nw] == INF:
                        dist[nh][nw] = d + 1
                        Q.append((nh,nw))
    if dist[gh][gw] != INF:
        print(dist[gh][gw])
    else:
        print(-1)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
from collections import deque

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
elif icase==1:
    h,w=4,4
    ch,cw=1,1
    dh,dw=4,4
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=['..#.', '..#.', '.#..', '.#..']   
elif icase==2:
    h,w=4,4
    ch,cw=1,4
    dh,dw=4,1
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=['.##.', '####', '####', '.##.']  
elif icase==3:
    h,w=4,5
    ch,cw=1,2
    dh,dw=2,5
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=['#.###', '####.', '#..##', '#..##'] 
elif icase==4:
    h,w=4,4
    ch,cw=2,2
    dh,dw=3,3
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=['....', '....', '....', '....']
        
icnt=-1
pair=[-1]*(h*w)
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            idx=i*w+j
#            pair.append(idx)
            pair[idx]=idx
#print("A",pair)
               
def root(x):
    if x==-1:
        return -1
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x
        
for i in range(h):
    for j in range(w):
        idx=i*w+j
        if s[i][j]==".":
            if i<h-1 and s[i+1][j]==".":
                idx1=(i+1)*w+j
                pair[idx1]=idx
            if j<w-1 and s[i][j+1]==".":
                idx1=i*w+j+1
                pair[idx1]=idx

for i in range(h):
    for j in range(w):
        idx=i*w+j
        if s[i][j]==".":
            if i<h-1 and s[i+1][j]==".":
                idx1=(i+1)*w+j
                unite(idx,idx1)
            if i>0 and s[i-1][j]==".":
                idx1=(i-1)*w+j
                unite(idx,idx1)
            if j<w-1 and s[i][j+1]==".":
                idx1=i*w+j+1
                unite(idx,idx1)
            if j>0 and s[i][j-1]==".":
                idx1=i*w+j-1
                unite(idx,idx1)

#print("B:",pair)
l=[root(ii) for ii in range(len(pair))]
#print("l:",l)
ll=list(set(l))    
ll.sort()
ll=ll[1:]
if len(ll)<1:
    print(0)
    sys.exit()

gg=[[] for i in range(max(ll)+1)]
for i in range(h):
    for j in range(w):
        idx=i*w+j
        if root(idx)!=-1:
            gg[root(idx)].append((i,j))        

ggg=[[] for i in range(max(ll)+1)]
for gi in gg:
    for gi2 in gg:
        if gi==gi2:
            continue
        for i,j in gi:
            idx=i*w+j
            for i2,j2 in gi2:
                idx2=i2*w+j2
                if root(idx2) in ggg[root(idx)]:
                    continue
                if abs(i-i2)<=2 and abs(j-j2)<=2:
                    ggg[root(idx)].append(root(idx2))
                    ggg[root(idx2)].append(root(idx))

#print("ll:",ll)
lenpair=len(ll)    
lenpair=max(ll)+1

qst=root(ch*w+cw)
qed=root(dh*w+dw)
q=deque([qst])

stack=[qst]
parent=[-1]*lenpair
parent[qst]=0
dist=[-1]*lenpair
dist[qst]=0
while q:
    state = q.popleft()
#    print("--- q:",q,"state:",state,"g:",g[state],"p:",parent)
    for v in ggg[state]:
#        print("  state:",state,"v:",v,"q:",q)
#        if parent[state] == v:
        if parent[v] !=-1:
            continue
        else:
#            print("parent:",parent,"xx:",xx,"stack",stack)
            parent[v]=state
            dist[v]=dist[state]+1
            q.append(v)
            if v==qed:
                print(dist[qed])   
                sys.exit()
#            print(" state:",state,"v:",v,"parent:",parent,"stack",stack,"dist[v]",dist[v])
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input=sys.stdin.readline
inf=float("inf")


def BFS():
    D=[[inf for _ in range(w)] for _ in range(h)]
    queue=deque()
    queue.append([Cx-1,Cy-1,0])
    D[Cx-1][Cy-1]=0

    while len(queue)>0:
        x,y,cnt=queue.popleft()
        for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
            X,Y=x+i,y+j
            if 0<=X<h and 0<=Y<w:
                if S[X][Y]=="." and D[X][Y]>cnt:
                    D[X][Y]=cnt
                    queue.append([X,Y,cnt])

        for X in range(max(0,x-2),min(h,x+3)):
            for Y in range(max(0,y-2),min(w,y+3)):
                if S[X][Y]=="." and D[X][Y]>cnt+1:
                    D[X][Y]=cnt+1
                    queue.append([X,Y,cnt+1])

    return D[Dx-1][Dy-1]


h,w=map(int,input().split())
Cx,Cy=map(int,input().split())
Dx,Dy=map(int,input().split())
S=[list(input()) for _ in range(h)]

D=BFS()
print(D if D!=inf else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
inf=float("inf")


def BFS():
    D=[[inf for _ in range(w)] for _ in range(h)]
    queue=deque()
    queue.append([Cx-1,Cy-1,0])
    D[Cx-1][Cy-1]=0

    while len(queue)>0:
        x,y,cnt=queue.popleft()
        for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
            X,Y=x+i,y+j
            if 0<=X<h and 0<=Y<w:
                if S[X][Y]=="." and D[X][Y]>cnt:
                    D[X][Y]=cnt
                    queue.append([X,Y,cnt])

        for X in range(max(0,x-2),min(h,x+3)):
            for Y in range(max(0,y-2),min(w,y+3)):
                if S[X][Y]=="." and D[X][Y]>cnt+1:
                    D[X][Y]=cnt+1
                    queue.append([X,Y,cnt+1])

    return D[Dx-1][Dy-1]


h,w=map(int,input().split())
Cx,Cy=map(int,input().split())
Dx,Dy=map(int,input().split())
S=[list(input()) for _ in range(h)]

D=BFS()
print(D if D!=inf else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readints():return list(map(int,readline().split()))

from collections import deque

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

dist = [10**10]*(h*w)

dq = deque()
dq.append(start)
dist[start] = 0

while dq:
    p = dq.popleft()
    y = p//w
    x = p%w
    for dy in range(-2,3):
        for dx in range(-2,3):
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                q = (y+dy)*w + x+dx
                if dist[q]<=dist[p]:
                    continue
                if abs(dy)+abs(dx)==1:
                    dq.appendleft(q)
                    dist[q] = dist[p]
                else:
                    dq.append(q)
                    dist[q] = dist[p] + 1

print(-1 if dist[goal]==10**10 else dist[goal])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def solve(H, W, Ch, Cw, Dh, Dw, maze):
    INF = 10 ** 12
    path = [[INF] * W for _ in range(H)]

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    q = deque()
    path[Ch][Cw] = 0
    q.append((Ch, Cw, 0))

    while q:
        y, x, s = q.popleft()
        for dy, dx in walk:
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and maze[ny][nx] == '.' and path[ny][nx] > s:
                path[ny][nx] = s
                if ny == Dh and nx == Dw:
                    break
                q.appendleft((ny, nx, s))
        for dy, dx in warp:
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and maze[ny][nx] == '.' and path[ny][nx] > s + 1:
                path[ny][nx] = s + 1
                if ny == Dh and nx == Dw:
                    break
                q.appendleft((ny, nx, s + 1))

    ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
    print(ans)


if __name__ == "__main__":
    H, W = map(int, input().split())
    Ch, Cw = map(lambda x: int(x) - 1, input().split())
    Dh, Dw = map(lambda x: int(x) - 1, input().split())
    maze = [input() for _ in range(H)]
    solve(H, W, Ch, Cw, Dh, Dw, maze)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def solve(H, W, Ch, Cw, Dh, Dw, maze):
    INF = 10 ** 12
    path = [[INF] * W for _ in range(H)]

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    q = deque()
    path[Ch][Cw] = 0
    q.append((Ch, Cw, 0))

    while q:
        y, x, s = q.popleft()
        for dy, dx in walk:
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and maze[ny][nx] == '.' and path[ny][nx] > s:
                path[ny][nx] = s
                q.appendleft((ny, nx, s))
        for dy, dx in warp:
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and maze[ny][nx] == '.' and path[ny][nx] > s + 1:
                path[ny][nx] = s + 1
                q.appendleft((ny, nx, s + 1))

    ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
    print(ans)


if __name__ == "__main__":
    H, W = map(int, input().split())
    Ch, Cw = map(lambda x: int(x) - 1, input().split())
    Dh, Dw = map(lambda x: int(x) - 1, input().split())
    maze = [input() for _ in range(H)]
    solve(H, W, Ch, Cw, Dh, Dw, maze)