Problem:


B: サイコロを転がさないで

問題文

$H$ 行 $W$ 列からなるグリッドがあります。以降、グリッド上の $i$ 行目 $j$ 列目のマスを $(i, j)$ のマスと書きます。

グリッドの各マスには、$1$ 以上 $6$ 以下の数字か、あるいは # の文字が $1$ つずつ書かれています。ただし、$i$ と $j$ がともに偶数であるような $(i, j)$ のマスには必ず # が書かれています。

あなたは以下の図で表されるようなサイコロを $1$ つ持っています。

最初、あなたはこのサイコロを底面が $6$, 前面が $2$, 右面が $3$ となるように $(1, 1)$ のマスに置きます。
ここで、前面は $(i, j)$ の $i$ が増える方向の面を、右面は $j$ が増える方向の面を指します。

その後、サイコロが置かれているマスに辺で隣接する $4$ マスのいずれかにサイコロを転がす操作を好きな回数繰り返すことができます。
サイコロを転がす際、サイコロは転がす方向に90度回転します。

ただし、サイコロを転がす際には以下の条件を満たしている必要があります。

グリッドの外にサイコロを転がしてはならない

# が書かれているマスに転がしてはならない

転がした後の状態を考えたときに、サイコロの底面に書かれた数字とそのマスに書かれた数字が一致する

$(1, 1)$ のマスには必ず $6$ が書かれていることが保証されます。

サイコロを転がす操作を繰り返すことで、サイコロを $(1, 1)$ のマスから $(H, W)$ のマスに移動させることができるか判定してください。

制約

$1 \leq H, W \leq 100$

グリッドの各マスには $1$ 以上 $6$ 以下の数字、または # が書かれている

$i, j$ がともに偶数となるような $(i, j)$ のマスには必ず # が書かれている

$(1, 1)$ には $6$ が書かれていることが保証される

入力

入力は以下の形式で標準入力から与えられる。

$H$ $W$
$s_{11}s_{12} \ldots s_{1W}$
$s_{21}s_{22} \ldots s_{2W}$
$\vdots$
$s_{H1}s_{H2} \ldots s_{HW}$

ここで、$s_{ij}$ は $(i, j)$ のマスにかかれている数字または文字を表す。
すなわち、$s_{ij}$ は $1$ 以上 $6$ 以下の数字であるか、あるいは # である。

出力

$(1, 1)$ のマスから $(H, W)$ のマスへサイコロを転がして移動させることができるならば YES を、そうでないならば NO を 1 行で出力せよ。

入力例 1

3 3
631
4#2
516

出力例 1

YES

$(1, 1), (1, 2), (1, 3), (2, 3), (3, 3)$ の順に転がすことで、到達可能です。

入力例 2

3 3
6#1
##2
516

出力例 2

NO

入力例 3

5 5
61244
2#5#3
14641
5#5#5
63126

出力例 3

YES



Sample input:
3 3
631
4#2
516


Sample output:
YES

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from collections import deque

h, w = map(int, input().split())
edge = [[] for _ in range(8 * w * h)]
field = []
for _ in range(h):
    line = input().rstrip()
    field.append(line)
if field[h-1][w-1] == "#":
    print("NO")
    exit()

def get_index(x, y, state):
    return x * w * 8 + y * 8 + state 

def get_place(index):
    x = index // (w * 8)
    index %= (w * 8)
    y = index // 8
    index %= 8
    state = index
    return x, y, state

if h % 2 == 0 and w % 2 == 0:
    print("NO")
    exit()
# 1: (2,3), (3,5), (5,4), (4,2) 
# 6: (5,3), (3,2), (2,4), (4,5) 
for x in range(h):
    for y in range(w):
        if field[x][y] in "#16":
            continue
        # Up - Down
        if x % 2 == 1 and y % 2 == 0 and x + 1 < h:
            if field[x-1][y] not in "#2345" and field[x+1][y] not in "#2345" and int(field[x-1][y]) + int(field[x+1][y]) == 7:
                path = int(field[x][y])
                # 0 -> 4, 6 -> 2
                if path == 2:
                    edge[get_index(x-1, y, 0)].append(get_index(x+1, y, 4))
                    edge[get_index(x-1, y, 6)].append(get_index(x+1, y, 2))
                    edge[get_index(x+1, y, 4)].append(get_index(x-1, y, 0))
                    edge[get_index(x+1, y, 2)].append(get_index(x-1, y, 6))
                # 1 -> 7, 5 -> 3
                if path == 3:
                    edge[get_index(x-1, y, 1)].append(get_index(x+1, y, 7))
                    edge[get_index(x-1, y, 5)].append(get_index(x+1, y, 3))
                    edge[get_index(x+1, y, 7)].append(get_index(x-1, y, 1))
                    edge[get_index(x+1, y, 3)].append(get_index(x-1, y, 5))
                # 3 -> 5, 7 -> 1
                if path == 4:
                    edge[get_index(x-1, y, 3)].append(get_index(x+1, y, 5))
                    edge[get_index(x-1, y, 7)].append(get_index(x+1, y, 1))
                    edge[get_index(x+1, y, 5)].append(get_index(x-1, y, 3))
                    edge[get_index(x+1, y, 1)].append(get_index(x-1, y, 7))
                # 2 -> 6, 4 -> 0
                if path == 5:
                    edge[get_index(x-1, y, 2)].append(get_index(x+1, y, 6))
                    edge[get_index(x-1, y, 4)].append(get_index(x+1, y, 0))
                    edge[get_index(x+1, y, 6)].append(get_index(x-1, y, 2))
                    edge[get_index(x+1, y, 0)].append(get_index(x-1, y, 4))
        # Right - Left
        if x % 2 == 0 and y % 2 == 1 and y + 1 < w:
            if field[x][y-1] not in "#2345" and field[x][y+1] not in "#2345" and int(field[x][y-1]) + int(field[x][y+1]) == 7:
                path = int(field[x][y])
                # 3 -> 7, 5 -> 1
                if path == 2:
                    edge[get_index(x, y-1, 3)].append(get_index(x, y+1, 7))
                    edge[get_index(x, y-1, 5)].append(get_index(x, y+1, 1))
                    edge[get_index(x, y+1, 7)].append(get_index(x, y-1, 3))
                    edge[get_index(x, y+1, 1)].append(get_index(x, y-1, 5))
                # 7 -> 3, 1 -> 5
                if path == 5:
                    edge[get_index(x, y-1, 7)].append(get_index(x, y+1, 3))
                    edge[get_index(x, y-1, 1)].append(get_index(x, y+1, 5))
                    edge[get_index(x, y+1, 3)].append(get_index(x, y-1, 7))
                    edge[get_index(x, y+1, 5)].append(get_index(x, y-1, 1))
                # 0 -> 6, 4 -> 2
                if path == 3:
                    edge[get_index(x, y-1, 0)].append(get_index(x, y+1, 6))
                    edge[get_index(x, y-1, 4)].append(get_index(x, y+1, 2))
                    edge[get_index(x, y+1, 6)].append(get_index(x, y-1, 0))
                    edge[get_index(x, y+1, 2)].append(get_index(x, y-1, 4))
                # 6 -> 0, 2 -> 4
                if path == 4:
                    edge[get_index(x, y-1, 6)].append(get_index(x, y+1, 0))
                    edge[get_index(x, y-1, 2)].append(get_index(x, y+1, 4))
                    edge[get_index(x, y+1, 0)].append(get_index(x, y-1, 6))
                    edge[get_index(x, y+1, 4)].append(get_index(x, y-1, 2))

visited = [False] * (8 * w * h)
def dfs(start):
    visited[start] = True
    for nv in edge[start]:
        if not visited[nv]:
            dfs(nv)
dfs(0)

if h % 2 == 1 and w % 2 == 1:
    ok = False
    for i in range(8):
        if visited[get_index(h-1, w-1, i)]:
            ok = True
    if ok:
        print("YES")
        exit()
    else:
        print("NO")
elif h % 2 == 0:
    if int(field[h-1][w-1]) == 2:
        if visited[get_index(h-2, w-1, 0)] or visited[get_index(h-2, w-1, 6)]:
            print("YES")
        else:
            print("NO")
    elif int(field[h-1][w-1]) == 3:
        if visited[get_index(h-2, w-1, 1)] or visited[get_index(h-2, w-1, 5)]:
            print("YES")
        else:
            print("NO")
    elif int(field[h-1][w-1]) == 4:
        if visited[get_index(h-2, w-1, 3)] or visited[get_index(h-2, w-1, 7)]:
            print("YES")
        else:
            print("NO")
    elif int(field[h-1][w-1]) == 5:
        if visited[get_index(h-2, w-1, 2)] or visited[get_index(h-2, w-1, 4)]:
            print("YES")
        else:
            print("NO")
elif w % 2 == 0:
    if int(field[h-1][w-1]) == 2:
        if visited[get_index(h-1, w-2, 3)] or visited[get_index(h-1, w-2, 5)]:
            print("YES")
        else:
            print("NO")
    elif int(field[h-1][w-1]) == 3:
        if visited[get_index(h-1, w-2, 0)] or visited[get_index(h-1, w-2, 4)]:
            print("YES")
        else:
            print("NO")
    elif int(field[h-1][w-1]) == 4:
        if visited[get_index(h-1, w-2, 2)] or visited[get_index(h-1, w-2, 6)]:
            print("YES")
        else:
            print("NO")
    elif int(field[h-1][w-1]) == 5:
        if visited[get_index(h-1, w-2, 1)] or visited[get_index(h-1, w-2, 7)]:
            print("YES")
        else:
            print("NO")
else:
    print("NO")

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
S = [input() for i in range(H)]

def tor(x,y):
    to = {'6':'3','3':'1','1':'4','4':'6'} if y%4==0 else {'6':'4','4':'1','1':'3','3':'6'}
    return to[S[y][x]]
def tol(x,y):
    to = {'6':'3','3':'1','1':'4','4':'6'} if y%4==2 else {'6':'4','4':'1','1':'3','3':'6'}
    return to[S[y][x]]
def tod(x,y):
    to = {'6':'2','2':'1','1':'5','5':'6'} if x%4==0 else {'6':'5','5':'1','1':'2','2':'6'}
    return to[S[y][x]]
def tou(x,y):
    to = {'6':'2','2':'1','1':'5','5':'6'} if x%4==2 else {'6':'5','5':'1','1':'2','2':'6'}
    return to[S[y][x]]
dxyto = [(0,1,tod),(1,0,tor),(0,-1,tou),(-1,0,tol)]
stack = [(0,0)]
visited = [[0]*W for i in range(H)]
while stack:
    x,y = stack.pop()
    visited[y][x] = 1
    if (x,y) == (W-1,H-1):
        print('YES')
        exit()
    c = S[y][x]
    for dx,dy,to in dxyto:
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if visited[ny][nx]: continue
        if S[ny][nx] == '#': continue
        if to(x,y) != S[ny][nx]: continue
        stack.append((nx,ny))
print('NO')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
H, W = map(int, input().split())
S = [[c for c in input()] for _ in range(H)]
B = [[False] * W for _ in range(H)]

R = [['6', '3', '1', '4'], ['1', '3', '6', '4']]
C = [['6', '2', '1', '5'], ['1', '2', '6', '5']]
G = [['6', '3', '1', '4'], ['2', '-1', '2', '-1'],
     ['1', '3', '6', '4'], ['5', '-1', '5', '-1']]

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


def dfs(y, x):
    if y < 0 or H <= y or x < 0 or W <= x:
        return
    if S[y][x] == '#':
        return
    if B[y][x] == True:
        return

    m4y = y % 4
    m4x = x % 4

    if S[y][x] != G[m4y][m4x]:
        return

    # R
    # if y % 2 == 0:
    #    if not(y % 4 != 0 or y % 4 == 0 and S[y][x] == R[0][x % 4]):
    #        return
    #    if not(y % 4 != 2 or y % 4 == 2 and S[y][x] == R[1][x % 4]):
    #        return
    # C
    # if y % 2 == 1:
    #    if not(y % 4 != 1 or y % 4 == 1 and S[y][x] == '2'):
    #        return
    #    if not(y % 4 != 3 or y % 4 == 3 and S[y][x] == '5'):
    #        return

    B[y][x] = True

    for i in range(4):
        dfs(y+dy[i], x+dx[i])


dfs(0, 0)
#print(*B, sep='\n')
print('YES' if B[H-1][W-1] else 'NO')

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
S = [list(input()) for i in range(H)]

A = [[False]*W for i in range(H)]

Q = [(0,0,(5,4,1,3,6,2))]

while Q:
    q = Q.pop()
    h,w,s = q[0],q[1],q[2]
    if min(h,w)<0 or h>=H or w>=W:continue
    if S[h][w]=="#":continue
    if A[h][w]:continue
    if int(S[h][w])!=s[4]:continue
    A[h][w] = True
    Q.append((h-1,w,(s[2],s[1],s[5],s[3],s[0],s[4])))
    Q.append((h+1,w,(s[4],s[1],s[0],s[3],s[5],s[2])))
    Q.append((h,w-1,(s[0],s[2],s[3],s[4],s[1],s[5])))
    Q.append((h,w+1,(s[0],s[4],s[1],s[2],s[3],s[5])))
print("YES" if A[H-1][W-1] else "NO")

Submission status: Accepted

Solution code:
from heapq import *
from collections import deque
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class Dice:
    def __init__(self,top,bot,lef,rig,fro,bac):
        self.top = top
        self.bot = bot
        self.lef = lef
        self.rig = rig
        self.fro = fro
        self.bac = bac

    def up(self):
        top, bac, bot, fro = self.fro, self.top, self.bac, self.bot
        return Dice(top,bot,self.lef,self.rig,fro,bac)

    def down(self):
        top, bac, bot, fro = self.bac, self.bot, self.fro, self.top
        return Dice(top,bot,self.lef,self.rig,fro,bac)

    def right(self):
        top, rig, bot, lef = self.lef, self.top, self.rig, self.bot
        return Dice(top,bot,lef,rig,self.fro,self.bac)

    def left(self):
        top, rig, bot, lef = self.rig, self.bot, self.lef, self.top
        return Dice(top,bot,lef,rig,self.fro,self.bac)

    def state(self):
        return (self.top, self.rig, self.bot, self.lef, self.fro, self.bac)

def main():
    h, w = MI()
    ss = [[0 if c == "#" else int(c) for c in SI()] for _ in range(h)]
    stack=[(0,0,Dice(1,6,4,3,2,5))]
    fin=[[set() for _ in range(w)] for _ in range(h)]
    fin[0][0].add(Dice(1,6,4,3,2,5).state())
    while stack:
        i,j,d=stack.pop()
        if i==h-1 and j==w-1:
            print("YES")
            exit()
        ni,nj=i-1,j
        if i-1>=0:
            nd=d.up()
            if nd.bot==ss[ni][nj] and nd.state() not in fin[ni][nj]:
                fin[ni][nj].add(nd.state())
                stack.append((i-1,j,nd))
        ni,nj=i+1,j
        if i+1<h:
            nd=d.down()
            if nd.bot==ss[ni][nj] and nd.state() not in fin[ni][nj]:
                fin[ni][nj].add(nd.state())
                stack.append((i+1,j,nd))
        ni,nj=i,j-1
        if j-1>=0:
            nd=d.left()
            if nd.bot==ss[ni][nj] and nd.state() not in fin[ni][nj]:
                fin[ni][nj].add(nd.state())
                stack.append((i,j-1,nd))
        ni,nj=i,j+1
        if j+1<w:
            nd=d.right()
            if nd.bot==ss[ni][nj] and nd.state() not in fin[ni][nj]:
                fin[ni][nj].add(nd.state())
                stack.append((i,j+1,nd))
    print("NO")

main()

Submission status: Accepted

Solution code:
def main():
    H, W = map( int, input().split())
    S = [ list( input()) for _ in range(H)]
    T = [[6,3,1,4], [2,0,2,0],[1,3,6,4],[5,0,5,0]]
    C = [[0]*W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if S[i][j] == '#':
                continue
            if T[i%4][j%4] == int(S[i][j]):
                C[i][j] = 1
    d = [(0,0)]
    P = [[False]*W for _ in range(H)]
    P[0][0] = True
    while d:
        x, y = d.pop()
        if x > 0:
            if C[x-1][y] == 1 and not P[x-1][y]:
                d.append((x-1,y))
                P[x-1][y] = True
        if x < H-1:
            if C[x+1][y] == 1 and not P[x+1][y]:
                d.append((x+1,y))
                P[x+1][y] = True
        if y > 0:
            if C[x][y-1] == 1 and not P[x][y-1]:
                d.append((x,y-1))
                P[x][y-1] = True
        if y < W-1:
            if C[x][y+1] == 1 and not P[x][y+1]:
                d.append((x,y+1))
                P[x][y+1] = True
    if P[H-1][W-1]:
        print("YES")
    else:
        print("NO")

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

dice = [[6,3,1,4],
        [2,0,2,0],
        [1,3,6,4],
        [5,0,5,0]]
H,W = map(int,input().split())
s = list(input() for _ in range(H))
board = [[0]*W for _ in range(H)]

def dfs(x,y):
    board[x][y] = 1
    for dx,dy in [[0,-1],[0,1],[1,0],[-1,0]]:
        if not(0 <= dx+x < H and 0 <= dy+y < W):
            continue
        if(board[x+dx][y+dy] == 1):
            continue

        if s[x+dx][y+dy] == str(dice[(x+dx)%4][(y+dy)%4]):
            dfs(dx+x,dy+y)

dfs(0,0)
print(["NO","YES"][board[-1][-1]])

Submission status: Accepted

Solution code:
from collections import deque

h,w = map(int,input().split())
g = [list(map(int, list(input().replace('#', '0')))) for _ in range(h)]
f = [[False]*w for _ in range(h)]
q = deque()
d = ((0,1), (1,0), (-1,0), (0,-1))

def chst(c,st,i):
  if i == 1:
    nc = st[1]
    nst = (st[0], 7-c)
  if i == 0:
    nc = st[0]
    nst = (7-c, st[1])
  if i == 2:
    nc = 7-st[1]
    nst = (st[0], c)
  if i == 3:
    nc = 7 - st[0]
    nst = (c, st[1])
  return nc, nst

q.append((0,0,(2,3)))
while q:
  y,x,st = q.popleft()
  if f[y][x]: continue
  f[y][x] = st
  for i in range(4):
    dx, dy = d[i]
    nx = x + dx; ny = y + dy
    if 0 <= nx < w and 0 <= ny < h:
      nc, nst = chst(g[y][x], st, i)
      if nc == g[ny][nx]:
        q.append((ny,nx,nst))
print('YES' if f[h-1][w-1] else 'NO')
# print(*f, sep = '\n')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(pow(10, 8))

S = [6, 3, 1, 4, 2, 5]
H, W = map(int, input().split())
X = []
for i in range(H):
    X.append(input().strip())

def migi(S):
    return [S[1], S[2], S[3], S[0], S[4], S[5]]
def hidari(S):
    return [S[3], S[0], S[1], S[2], S[4], S[5]]
def sita(S):
    return [S[4], S[1], S[5], S[3], S[2], S[0]]
def ue(S):
    return [S[5], S[1], S[4], S[3], S[0], S[2]]

vs = set()

def dfs(x, y, s):
    if (x, y) == (H-1, W-1):
        return True
    vs.add((x, y))
    f = False
    if x+1 < H and (x+1, y) not in vs:
        ns = sita(s)
        if str(ns[0]) == X[x+1][y]:
            f = f|dfs(x+1, y, ns)
    if y+1 < W and (x, y+1) not in vs:
        ns = migi(s)
        if str(ns[0]) == X[x][y+1]:
            f = f|dfs(x, y+1, ns)
    if x-1 >= 0 and (x-1, y) not in vs:
        ns = ue(s)
        if str(ns[0]) == X[x-1][y]:
            f = f|dfs(x-1, y, ns)
    if y-1 >= 0 and (x, y-1) not in vs:
        ns = hidari(s)
        if str(ns[0]) == X[x][y-1]:
            f = f|dfs(x, y-1, ns)
    return f
if dfs(0, 0, S):
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

d = [(1,0),(-1,0),(0,1),(0,-1)]
def solve():
    def rotate(dice,d):
        d1,d2,d3,d4,d5,d6 = dice
        if d == (0,1):
            return (d4,d2,d1,d6,d5,d3)
        elif d == (0,-1):
            return (d3,d2,d6,d1,d5,d4)
        elif d == (1,0):
            return (d5,d1,d3,d4,d6,d2)
        else:
            return (d2,d6,d3,d4,d1,d5)
    h,w = LI()
    s = [input() for i in range(h)]
    bfs = [[0 for i in range(w)] for j in range(h)]
    bfs[0][0] = 1
    q = deque([(0,0,(1,2,3,4,5,6))])
    while q:
        y,x,dice = q.popleft()
        if y == h-1 and x == w-1:
            print("YES")
            return
        for dy,dx in d:
            ny,nx = y+dy,x+dx
            if 0 <= ny < h and 0 <= nx < w:
                nd = rotate(dice,(dy,dx))
                if not bfs[ny][nx] and str(nd[-1]) == s[ny][nx]:
                    bfs[ny][nx] = 1
                    q.append((ny,nx,nd))
    print("NO")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

H, W = map(int, readline().split())

Gr = [list(map(lambda x: int(x) if x != '#' else 7, readline().strip())) for _ in range(H)]

Ri = []
for h in range(H):
    if h % 4 == 0:
        Ri.append([6, 3, 1, 4]*W)
    elif h % 4 == 1:
        Ri.append([2, 8, 2, 8]*W)
    elif h % 4 == 2:
        Ri.append([1, 3, 6, 4]*W)
    else:
        Ri.append([5, 8, 5, 8]*W)

for h in range(H):
    for w in range(W):
        if Gr[h][w] != Ri[h][w]:
            Gr[h][w] = -1

stack = [(0, 0)]
used = set(stack)
dim = [(0, -1), (0, 1), (1, 0), (-1, 0)]
while stack:
    nx, ny = stack.pop()
    for dx, dy in dim:
        fx, fy = nx+dx, ny+dy
        if not 0 <= fx < W or not 0 <= fy < H:
            continue
        if Gr[fy][fx] == -1:
            continue
        if (fx, fy) in used:
            continue
        used.add((fx, fy))
        stack.append((fx, fy))
print('YES' if (W-1, H-1) in used else 'NO')

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
MAP=[input() for i in range(H)]

CANGO=[[0]*W for i in range(H)]
CANGO[0][0]=1

Q=[(0,0)]

while Q:
    x,y=Q.pop()

    for tox,toy in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:
        if 0<=tox<H and 0<=toy<W and CANGO[tox][toy]==0:
            if tox%4==0:
                if toy%4==0 and MAP[tox][toy]=="6":
                    CANGO[tox][toy]=1
                    Q.append((tox,toy))
                if toy%4==1 and MAP[tox][toy]=="3":
                    CANGO[tox][toy]=1
                    Q.append((tox,toy))
                if toy%4==2 and MAP[tox][toy]=="1":
                    CANGO[tox][toy]=1
                    Q.append((tox,toy))
                if toy%4==3 and MAP[tox][toy]=="4":
                    CANGO[tox][toy]=1
                    Q.append((tox,toy))
            if tox%4==2:
                if toy%4==0 and MAP[tox][toy]=="1":
                    CANGO[tox][toy]=1
                    Q.append((tox,toy))
                if toy%4==1 and MAP[tox][toy]=="3":
                    CANGO[tox][toy]=1
                    Q.append((tox,toy))
                if toy%4==2 and MAP[tox][toy]=="6":
                    CANGO[tox][toy]=1
                    Q.append((tox,toy))
                if toy%4==3 and MAP[tox][toy]=="4":
                    CANGO[tox][toy]=1
                    Q.append((tox,toy))
            if tox%4==1:
                if toy%4==0 and MAP[tox][toy]=="2":
                    CANGO[tox][toy]=1
                    Q.append((tox,toy))

                if toy%4==2 and MAP[tox][toy]=="2":
                    CANGO[tox][toy]=1
                    Q.append((tox,toy))
            if tox%4==3:
                if toy%4==0 and MAP[tox][toy]=="5":
                    CANGO[tox][toy]=1
                    Q.append((tox,toy))

                if toy%4==2 and MAP[tox][toy]=="5":
                    CANGO[tox][toy]=1
                    Q.append((tox,toy))

if CANGO[H-1][W-1]==1:
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
h, w = map(int, input().split())

p = list(range(h*w))

def find(x):
    global p
    if p[x] == x:return x
    p[x] = find(p[x])
    return p[x]

def unite(x, y):
    global p
    x = find(x)
    y = find(y)
    if x != y:p[x] =y

def real_number(i, j):
    i += 1
    j += 1
    i %= 4
    j %= 4
    if i == 1 and j == 1:return 6
    if i == 1 and j == 2:return 3
    if i == 1 and j == 3:return 1
    if i == 1 and j == 0:return 4
    if i == 2 and j == 1:return 2
    if i == 2 and j == 3:return 2
    if i == 3 and j == 1:return 1
    if i == 3 and j == 2:return 3
    if i == 3 and j == 3:return 6
    if i == 3 and j == 0:return 4
    if i == 0 and j == 1:return 5
    if i == 0 and j == 3:return 5
    return -1
    
field = [input() for i in range(h)]
for i in range(h):
    for j in range(w):
        if str(real_number(i,j)) != field[i][j]:continue
        if i + 1 < h and str(real_number(i+1,j)) == field[i+1][j]:
            unite(i*w+j, (i+1)*w+j)
        if j + 1 < w and str(real_number(i,j+1)) == field[i][j+1]:
            unite(i*w+j, i*w+j+1)

if find(0) == find(h*w-1):
    print("YES")
else:
    print("NO")