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:
from collections import deque

H, W = map(int, input().split())
CH, CW = map(int, input().split())
DH, DW = map(int, input().split())
CH = CH - 1
CW = CW - 1
DH = DH - 1
DW = DW - 1
s = (CH,CW)
g = (DH,DW)

S = [0 for i in range(0,H)]
for i in range(0,H):
    a = input()
    S[i] = [a[i:i+1] for i in range(len(a))]
    
nohani = [(2,2),(2,3),(2,1),(3,2),(1,2)]
hani = []
for i in range(5):
    for j in range(5):
      if (i,j) not in nohani:   
         hani.append((i-2,j-2))

maze_adj_maho = {}
for x in range(H):
  for y in range(W):
    l = []
    for (dx,dy) in hani:
      if (0<=x+dx<W) and (0<=y+dy<H) and S[x+dx][y+dy]!='#':
        l.append((x+dx,y+dy))
    maze_adj_maho[(x,y)] = l

maze_adj = {}
for x in range(H):
  for y in range(W):
    l = []
    for (dx,dy) in [(1,0),(0,1),(-1,0),(0,-1)]: 
      if (0<=x+dx<W) and (0<=y+dy<H) and S[x+dx][y+dy]!='#':
        l.append((x+dx,y+dy))
    maze_adj[(x,y)] = l

def bfs(adj,adj2,v,S):
  prev = {} # 直前にどの頂点を訪れたか
  dist = {} # 距離
  for i in range(H):
      for j in range(W):
          dist[(i,j)] = 10000000
  queue = deque([(v,0,'start')]) # vを距離0の初期点として訪れることを予約
  while queue:
    v,d,p = queue.popleft() # キューの最初の要素を取り出す
    if v in prev: continue # vを訪問済みなら次の要素へ
    prev[v] = p # 訪問済みでなければpからvへ訪問したと記録
    dist[v] = min(d,dist[v]) # 距離はdであると記録
    for u in adj[v]:
        if u in queue:
          queue.append((u,d,v)) # 後でuを訪問することを予約
    for u in adj2[v]:
      if u not in adj[v]:
       if u not in prev:
          if u not in queue:
            queue.append((u,d+1,v)) # 後でuを訪問することを予約
        
  for i in range(H):
      for j in range(W):
          if dist[(i,j)] == 10000000:
              dist[(i,j)] = -1
  return prev,dist

prev,dist = bfs(maze_adj,maze_adj_maho,s,S)
print (dist)
print (dist[g])

Submission status: Runtime Error

Solution code:
H,W = map(int,input().split())
CH,CW = map(int,input().split())
DH,DW = map(int,input().split())
S=[None]*H
for i in range(H):
    S[i] = input()

from collections import deque
def cango_step(x,y):
    cand =[]
    if x+1<=H-1:
        cand.append((x+1,y))
    if x-1>=0:
        cand.append((x-1,y))
    if y+1<=W-1:
        cand.append((x,y+1))
    if y-1>=0:
        cand.append((x,y-1))
    return cand
def cango_warp(x,y):
    cand = [(i,j) 
            for i in range(x-2,x+3) for j in range(y-2,y+3) 
            if 0<=i and i<=H-1 and 0<=j and j<=W-1]
    return cand

been = [[False]*W for _ in range(H)]
rooms=dict()
i_room=-1
for x in range(H):
    for y in range(W):
        if S[x][y]=="." and not been[x][y]:
            i_room+=1
            been[x][y]=True
            q = deque([(-1,-1,x,y)]) 

            rooms[(x,y)]=i_room
            while q:
                x_old,y_old,x_now,y_now = q.popleft()
                
                cand = cango_step(x_now,y_now)
                #print(x_old,y_old,x_now,y_now,time)
                
                if x_now==CH-1 and y_now==CW-1:
                    start_warp = i_room
                if x_now==DH-1 and y_now==DW-1:
                    end_warp = i_room
                
                for x_new,y_new in cand:
                    if not been[x_new][y_new] and S[x_new][y_new]==".":
                        q.append((x_now,y_now,x_new,y_new))
                        been[x_new][y_new]=True
#                        room.append((x_new,y_new))
                        rooms[(x_new,y_new)]=i_room
#            rooms.append(room)

if start_warp==end_warp:
    print(0)
else:
        
    #ワープで行けるほかの部屋をtree入れる
    n_rooms = i_room+1
    tree=[[] for _ in range(n_rooms)]
    
    i_loop=0
    for k,v in rooms.items():
        i_loop+=1
        cango = set(rooms[togo] for togo in cango_warp(*k) if S[togo[0]][togo[1]]=="." )
        for c in cango:
            if c!=v:
                tree[c].append(v)
                tree[v].append(c)
        if i_loop%1000==0:
                for i in range(len(tree)):
                    tree[i] = set(tree[i])
        #print(v,cango)

        
    for i in range(len(tree)):
        tree[i] = set(tree[i])
    
    
    q = deque([(-1,start_warp,0)]) #これでもよい
    
    been=[False]*n_rooms
    been[start_warp]=True
    reach=False
    while q:
        parent,x,time = q.popleft()
        if x==end_warp:
            reach=True
            break
        
        for y in tree[x]:
            if not been[y]:
                q.append((x,y,time+1))#子ノードを追加
                been[y]=True
        #print(parent,x,q,time)
    if reach:
        print(time)
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
def cost(x, y, gx, gy):
  #printmap(map, x, y, gx, gy)
  
  if x == gx and y == gy:
    return 0
  elif x < gx and y < gy:
    if map[y][x+1] == '.':
      return cost(y, x+1, gx, gy)
    elif map[y+1][x] == '.':
      return cost(y+1, x, gx, gy)
  elif x < gx and y >= gy:
    if map[y][x+1] == '.':
      return cost(y, x+1, gx, gy)
    elif y != gy and map[y-1][x] == '.':
      return cost(y-1, x, gx, gy)
  elif x >= gx and y < gy:
    if map[y+1][x] == '.':
      return cost(y+1, x, gx, gy)
    elif x != gx and map[1][x-1] == '.':
      return cost(y, x-1, gx, gy)
  elif x >= gx and y >= gy:
    if x != gx and map[1][x-1] == '.':
      return cost(y, x-1, gx, gy)
    elif y != gy and map[y-1][x] == '.':
      return cost(y-1, x, gx, gy)
    
  temp = warp(x, y, gx, gy)
  if temp is None:
    return None
  else:
    c = cost(temp[0], temp[1], gx, gy)
    if c is None:
      return None
    else:
      return c + 1
    
def warp(x, y, gx, gy):
  #print('warp!', x, y, gx, gy)
  for i in range(x-2, x+3):
    for j in range(y-2, y+3):
      if x <= i <= gx and y <= j <= gy and (x != i or y != j) and map[j][i] == '.':
        return (i , j)
  
  return None

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

map = []
for i in range(h):
  s = list(input())
  s.insert(0, '#')
  s.append('#')
  map.append(s)
map.insert(0, ['#'] * (w + 2))
map.append(['#'] * (w + 2))

result = cost(cw, ch, dw, dh)
if result is None:
  print(-1)
else:
  print(result)

Submission status: Runtime Error

Solution code:
h, w, m = map(int, input().split())
hwList = [[0] * (w + 1) for i in range(h + 1)]
hList = [0] * (h + 1)
wList = [0] * (w + 1)
for x in range(m):
    h_i, w_i = map(int, input().split())
    hList[h_i] += 1
    wList[w_i] += 1
    hwList[h_i][w_i] += 1
h_max = max(hList)
w_max = max(wList)
h_maxid = [i for i, v in enumerate(hList) if v == h_max]
w_maxid = [i for i, v in enumerate(wList) if v == w_max]
isminus = 1
if len(h_maxid) * len(w_maxid) > 3 * (10 ** 5): isminus = 0
else:
    for a in h_maxid:
        if isminus == 0: break
        for b in w_maxid:
            if hwList[b][a] == 1: continue
            isminus = 0
            break
print(h_max + w_max - isminus)

Submission status: Runtime Error

Solution code:
import itertools
import math
import sys
import heapq

h, w = map(int, input().split())
Ch, Cw = map(int, input().split()) #start
Dh, Dw = map(int, input().split()) #goal
s = [input() for _ in range(w)]

x, y = Ch, Cw
cnt = 0

def WallCheck(s, x, y):
    if s[x][y-1] == ".":
        return True
    elif s[x+1][y] == ".":
        return True
    elif s[x][y+1] == ".":
        return True
    elif s[x-1][y] == ".":
        return True
    else:
        return False

def WarpCheck(s, x, y):
    for i in range(-2, 3):
        for j in range(-2, 3):
            if s[(x-i)][(y-j)] == "." and i == j == 0:
                return True
    return False

def Manhattan(x, y):
    return math.sqrt(pow(x -Dh, 2) + pow(y-Dw, 2))

def Move(s, x, y, n):
    next = []
    for i in range(-n, n+1):
        for j in range(-n, n+1):
            if s[(x-i)][(y-j)] == "." and i == j == 0:
                next.append([i, j])

    min_x, min_y = 100, 100
    for i in range(len(next)):
        Manhattan(next[i][0], next[i][1])
        if min_x + min_y >= Manhattan(next[i][0], next[i][1]):
            min_x, min_y = next[i][0], next[i][1]
    return min_x, min_y

def GoalCheck(s, x, y):
    if x == Dh and y == Dw:
        return True
    else:
        return False
    
while True:
        if not WallCheck(s, x, y):
            if not WarpCheck(s, x, y):
                print(-1)
                exit()
            else:
                # ワープ処理
                x, y = Move(s, x, y, 2)
                cnt += 1
        else:
            # 歩く
            x, y = Move(s, x, y, 1)
        
        if GoalCheck(s, x, y):
            print(cnt)
            exit()

Submission status: Runtime Error

Solution code:
from itertools import product
from collections import deque
import numpy as np
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

X = iter(open(0).readlines())
h, w = map(int, next(X).split())
ch, cw = map(int, next(X).split())
dh, dw = map(int, next(X).split())
dp = Grid([x.strip() for x in X], function=lambda x: 10**6 if x == '.' else -1)

def dfs(stack):
    if not stack:
        return
    x, y, d = stack[0]
    dp[y, x] = d
    stack2 = []
    while stack:
        x, y, d = stack.pop()
        if dp[y, x] < d:
            continue
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+dx, y+dy
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d:
                dp[ny, nx] = d
                stack.append((nx, ny, d))
        for dx, dy in product(range(-2, 3), repeat=2):
            if abs(dx) + abs(dy) < 2:
                continue
            nx, ny = x+dx, y+dy                
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d+1:
                dp[ny, nx] = d+1
                stack2.append((nx, ny, d+1))
    dfs(stack2)

dfs([(cw-1, ch-1, 0)])
if dp[dh-1, dw-1] == 10**6:
    print(-1)
else:
    print(dp[dh-1, dw-1])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python

from typing import List


def dump_s(s: list) -> None:
    print("dump_s:")
    for h_index in range(1, len(s)):
        print(''.join(s[h_index]))


def fill(h: int, w: int, c_h: int, c_w: int, s: list, fill_char: str = 'o') -> list:
    ret = list()
    if s[c_h][c_w] == '.':
        s[c_h][c_w] = fill_char
        ret.append((c_h, c_w,))
    if c_h > 1 and s[c_h - 1][c_w] == '.':
        ret.extend(fill(h, w, c_h - 1, c_w, s, fill_char))
    if c_h < h and s[c_h + 1][c_w] == '.':
        ret.extend(fill(h, w, c_h + 1, c_w, s, fill_char))
    if c_w > 1 and s[c_h][c_w - 1] == '.':
        ret.extend(fill(h, w, c_h, c_w - 1, s, fill_char))
    if c_w < w and s[c_h][c_w + 1] == '.':
        ret.extend(fill(h, w, c_h, c_w + 1, s, fill_char))
    return ret


def f(h: int, w: int, c_h: int, c_w: int, d_h: int, d_w: int, s: list) -> int:
    # move a
    filled = fill(h, w, c_h, c_w, s)
    for t in filled:
        if t[0] == d_h and t[1] == d_w:
            return 0

    # move b
    wp_candidate_dic = dict()
    for t in filled:
        h0 = t[0] - 2 if t[0] - 2 >= 1 else 1
        w0 = t[1] - 2 if t[1] - 2 >= 1 else 1
        h1 = t[0] + 2 if t[0] + 2 <= h else h
        w1 = t[1] + 2 if t[1] + 2 <= w else w
        for h_index in range(h0, h1+1):
            for w_index in range(w0, w1+1):
                wp = (h_index, w_index)
                if wp not in wp_candidate_dic and s[h_index][w_index] == '.':
                    wp_candidate_dic[wp] = True

    for t in wp_candidate_dic:
        filled_x = fill(h, w, t[0], t[1], s, 'x')
        for pt in filled_x:
            if pt[0] == c_h and pt[1] == c_w:
                return 1
        for pt in filled_x:
            s[pt[0]][pt[1]] = '.'

    ret_min = None
    for t in wp_candidate_dic:
        ret = f(h, w, t[0], t[1], d_h, d_w, s)
        if ret >= 0 and (ret_min is None or ret_min > ret):
            ret_min = ret
    if ret_min is not None:
        return ret_min + 1

    return -1


if __name__ == '__main__':
    h, w = list(map(lambda x: int(x), input().split()))
    c_h, c_w = list(map(lambda x: int(x), input().split()))
    d_h, d_w = list(map(lambda x: int(x), input().split()))
    s: List[list] = list()
    s.append(list())
    for h_index in range(1, h+1):
        rec = list(input())
        rec.insert(0, '')
        s.append(rec)
    print(f(h, w, c_h, c_w, d_h, d_w, s))

Submission status: Runtime Error

Solution code:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);

        Problem solver = new Problem();
        solver.solve(0, in, out);
        out.close();
    }

    static class Problem {

        private final int[][] DIRS = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

        private final int[][] DIA = {
                {-1, -1}, {1, 1},{1, -1}, {-1, 1},
                {2, 0}, {0, 2}, {-2, 0}, {0, -2},
                {2, 1}, {1, 2}, {2, -1}, {-1, 2},
                {-2, 1}, {1, -2}, {-2, -1}, {-1, -2},
                {2, -2}, {-2, 2}, {2, 2}, {-2, -2}
        };


        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int R = in.nextInt(), C = in.nextInt();
            int startX = in.nextInt() - 1, startY = in.nextInt() - 1;
            int endX = in.nextInt() - 1, endY = in.nextInt() - 1;

            int[][] matrix = new int[R][C];
            for(int i = 0; i < R; i++) {
                String s = in.next();
                for(int j = 0; j < s.length(); j++) {
                    matrix[i][j] = s.charAt(j) == '.' ? 0 : 1;
                }
            }

            int[][] dp = new int[R][C];
            for(int[] row : dp) {
                Arrays.fill(row, -1);
            }
            
            int res = minMoves(matrix, startX, startY, endX, endY, dp);
            out.println(res == Integer.MAX_VALUE ? -1 : res);
        }

        public int minMoves(int[][] matrix, int i, int j, int targetX, int targetY, int[][] dp) {
            if(i == targetX && j == targetY)
                return 0;

            if(dp[i][j] != -1) return dp[i][j];
            
            matrix[i][j] = 2; // marked

            int res = Integer.MAX_VALUE;
            for(int[] dir : DIRS) {
                int x = i + dir[0], y = j + dir[1];
                if(isValid(matrix, x, y) && matrix[x][y] == 0)
                    res = Math.min(res, minMoves(matrix, x, y, targetX, targetY, dp));
            }

            if(res == Integer.MAX_VALUE) {
                for (int[] dir : DIA) {
                    int x = i + dir[0], y = j + dir[1];
                    if(isValid(matrix, x, y) && matrix[x][y] == 0) {
                        int curr = minMoves(matrix, x, y, targetX, targetY, dp);
                        if(curr != Integer.MAX_VALUE) curr++;
                            res = Math.min(res, curr);
                    }

                }
            }

            matrix[i][j] = 0; // Un-marked
            dp[i][j] = res;
            return res;
        }

        public boolean isValid(int[][] matrix, int i, int j) {
            return !(i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length);
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}