Problem:


Score : 1200 points

Problem Statement

In Takaha-shi, the capital of Republic of AtCoder, there are N roads extending east and west, and M roads extending north and south. There are no other roads.
The i-th east-west road from the north and the j-th north-south road from the west cross at the intersection (i, j).
Two east-west roads do not cross, nor do two north-south roads.
The distance between two adjacent roads in the same direction is 1.

Each road is one-way; one can only walk in one direction. The permitted direction for each road is described by a string S of length N and a string T of length M, as follows:

If the i-th character in S is W, one can only walk westward along the i-th east-west road from the north;

If the i-th character in S is E, one can only walk eastward along the i-th east-west road from the north;

If the i-th character in T is N, one can only walk northward along the i-th north-south road from the west;

If the i-th character in T is S, one can only walk southward along the i-th south-west road from the west.

Process the following Q queries:

In the i-th query, a_i, b_i, c_i and d_i are given. What is the minimum distance to travel to reach the intersection (c_i, d_i) from the intersection (a_i, b_i) by walking along the roads?

Constraints

2 \leq N \leq 100000

2 \leq M \leq 100000

2 \leq Q \leq 200000

|S| = N

S consists of W and E.

|T| = M

T consists of N and S.

1 \leq a_i \leq N

1 \leq b_i \leq M

1 \leq c_i \leq N

1 \leq d_i \leq M

(a_i, b_i) \neq (c_i, d_i)

Input

Input is given from Standard Input in the following format:

N M Q
S
T
a_1 b_1 c_1 d_1
a_2 b_2 c_2 d_2
:
a_Q b_Q c_Q d_Q

Output

In the i-th line, print the response to the i-th query. If the intersection (c_i, d_i) cannot be reached from the intersection (a_i, b_i) by walking along the roads, print -1 instead.

Sample Input 1

4 5 4
EEWW
NSNNS
4 1 1 4
1 3 1 2
4 2 3 2
3 3 3 5

Sample Output 1

6
11
5
4

The permitted direction for each road is shown in the following figure (north upward):

For each of the four queries, a route that achieves the minimum travel distance is as follows:

Sample Input 2

3 3 2
EEE
SSS
1 1 3 3
3 3 1 1

Sample Output 2

4
-1

The travel may be impossible.

Sample Input 3

9 7 10
EEEEEWEWW
NSSSNSN
4 6 9 2
3 7 6 7
7 5 3 5
1 1 8 1
4 3 5 4
7 4 6 4
2 5 8 6
6 6 2 7
2 4 7 5
7 2 9 7

Sample Output 3

9
-1
4
9
2
3
7
7
6
-1



Sample input:
4 5 4
EEWW
NSNNS
4 1 1 4
1 3 1 2
4 2 3 2
3 3 3 5


Sample output:
6
11
5
4

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    def __init__(self, graph, start):
        self.g = graph.graph
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        self.prev = defaultdict(lambda: None)

        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]
      
n, m, q = list(map(int, input().split()))
s = list(input()) 
t = list(input())     

inputs = []
for i, s_ in enumerate(s):
  if s_=="E":
    inputs += [(i*m+j, i*m+j+1, 1) for j in range(0,m-1)]
  else:
    inputs += [(i*m+j, i*m+j-1, 1) for j in range(m-1,0,-1)]
for i, t_ in enumerate(t):
  if t_=="N":
    inputs += [(j*m+i, (j-1)*m+i, 1) for j in range(m-1,0,-1)]
  else:
    inputs += [(j*m+i, (j+1)*m+i, 1) for j in range(0, m-1)]
g = Graph()
for src, dst, weight in inputs:
    g.add_edge(src, dst, weight)

for i in range(q):
  a, b, c, d = list(map(int, input().split()))
  dij = Dijkstra(g, (a-1)*m+b-1)
  dist = dij.shortest_distance((c-1)*m+d-1)
  if dist!=float('inf'):
    print(dist)
  else:
    print(-1)

Submission status: Runtime Error

Solution code:
def read():
    N, M, Q = map(int, input().split(' '))
    S = input()
    T = input()
    qs = []
    for _ in range(N):
      a, b, c, d = map(int, input().split(' '))
      qs.append((a, b, c, d))
    return N, M, Q, S, T, qs


DS = {'W': (-1, 0), 'E': (1, 0), 'N': (0, -1), 'S': (0, 1)}


def ans_q(N, M, Q, S, T, a, b, c, d):
    # ds[i][j] スタート地点からの距離(未達は-1)
    ds = [[-1 for _ in range(M)] for _ in range(N)]
    q = [(a-1, b-1)]
    ds[a-1][b-1] = 0
    while q:
        i, j = q.pop()
        dd = ds[i][j]
        drs = [DS.get(s) for s in [S[i], T[j]]]
        for dx, dy in drs:
            i2 = i + dy
            j2 = j + dx
            if i2 < 0 or i2 >= N or j2 < 0 or j2 >= M:
                continue
            if ds[i2][j2] >= 0 and ds[i2][j2] <= dd + 1:
                continue
            ds[i2][j2] = dd + 1
            q.append((i2, j2))
    return ds[c-1][d-1]


if __name__ == '__main__':
    N, M, Q, S, T, qs = read()
    for a, b, c, d in qs:
        print(ans_q(N, M, Q, S, T, a, b, c, d))

Submission status: Runtime Error

Solution code:
def read():
    N, M, Q = map(int, input().split(' '))
    S = input()
    T = input()
    qs = []
    for _ in range(N):
      a, b, c, d = map(int, input().split(' '))
      qs.append((a, b, c, d))
    return N, M, Q, S, T, qs


DS = {'W': (-1, 0), 'E': (1, 0), 'N': (0, -1), 'S': (0, 1)}


def ans_q(N, M, Q, S, T, a, b, c, d):
    # ds[i][j] スタート地点からの距離(未達は-1)
    ds = [[-1 for _ in range(M)] for _ in range(N)]
    q = [(a-1, b-1)]
    ds[a-1][b-1] = 0
    while q:
        i, j = q.pop()
        dd = ds[i][j]
        drs = [DS.get(s) for s in [S[i], T[j]]]
        for dx, dy in drs:
            i2 = i + dy
            j2 = j + dx
            if i2 < 0 or i2 >= N or j2 < 0 or j2 >= M:
                continue
            if ds[i2][j2] >= 0 and ds[i2][j2] <= dd + 1:
                continue
            ds[i2][j2] = dd + 1
            q.append((i2, j2))
    return ds[c-1][d-1]


if __name__ == '__main__':
    for a, b, c, d in qs:
        print(ans_q(N, M, Q, S, T, a, b, c, d))

Submission status: Runtime Error

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

import itertools
import time
import numpy as np


N, M, Q = [int(x) for x in input().split(" ")]
S = input()
T = input()


def is_outside(pos):
    return pos[0] < 0 or pos[0] >= N \
            or pos[1] < 0 or pos[1] >= M


def argmin_positive(array):
    pmin = M * N
    pargmin = (-1, -1)
    for i, j in itertools.product(range(N), range(M)):
        v = array[i, j]
        if pmin > v > 0:
            pmin = v
            pargmin = (i, j)
    return pargmin


def fn(a, b, c, d):
    distance = np.full((N, M), M*N, dtype=np.int32)
    updated = np.zeros((N, M), dtype=np.int8)
    src = (a - 1, b - 1)
    dst = (c - 1, d - 1)
    focused = src
    distance[src[0], src[1]] = 0
    while focused != dst:
        # time.sleep(0.5)
        # print(distance)
        # print(updated)
        # print(focused)

        d = distance[focused[0], focused[1]]
        horizontal_next = (focused[0],
                           focused[1] + (1 if S[focused[0]] is "E" else -1))
        vertical_next = (focused[0] + (1 if T[focused[1]] is "S" else -1),
                         focused[1])

        try:
            if not is_outside(vertical_next):
                vd = distance[vertical_next[0], vertical_next[1]]
                if vd > d + 1:
                    distance[vertical_next[0], vertical_next[1]] = d + 1
                    updated[vertical_next[0], vertical_next[1]] = 1
        except IndexError:
            pass

        try:
            if not is_outside(horizontal_next):
                hd = distance[horizontal_next[0], horizontal_next[1]]
                if hd > d + 1:
                    distance[horizontal_next[0], horizontal_next[1]] = d + 1
                    updated[horizontal_next[0], horizontal_next[1]] = 1
        except IndexError:
            pass

        updated[focused[0], focused[1]] = 0
        if np.max(updated) == 0:
            print(-1)
            return
        # focused = tuple(np.unravel_index(np.argmin(distance * updated,
        #                                           axis=None),
        #                                 distance.shape))
        focused = argmin_positive(distance * updated)
    print(distance[dst[0], dst[1]])


for _ in range(Q):
    a, b, c, d = [int(x) for x in input().split(" ")]
    fn(a, b, c, d)