Problem:


Score : 400 points

Problem Statement

There are N squares arranged in a row, numbered 1, 2, ..., N from left to right.
You are given a string S of length N consisting of . and #. If the i-th character of S is #, Square i contains a rock; if the i-th character of S is ., Square i is empty.

In the beginning, Snuke stands on Square A, and Fnuke stands on Square B.

You can repeat the following operation any number of times:

Choose Snuke or Fnuke, and make him jump one or two squares to the right. The destination must be one of the squares, and it must not contain a rock or the other person.

You want to repeat this operation so that Snuke will stand on Square C and Fnuke will stand on Square D.

Determine whether this is possible.

Constraints

4 \leq N \leq 200\ 000

S is a string of length N consisting of . and #.

1 \leq A, B, C, D \leq N

Square A, B, C and D do not contain a rock.

A, B, C and D are all different.

A < B

A < C

B < D

Input

Input is given from Standard Input in the following format:

N A B C D
S

Output

Print Yes if the objective is achievable, and No if it is not.

Sample Input 1

7 1 3 6 7
.#..#..

Sample Output 1

Yes

The objective is achievable by, for example, moving the two persons as follows. (A and B represent Snuke and Fnuke, respectively.)

A#B.#..

A#.B#..

.#AB#..

.#A.#B.

.#.A#B.

.#.A#.B

.#..#AB

Sample Input 2

7 1 3 7 6
.#..#..

Sample Output 2

No

Sample Input 3

15 1 3 15 13
...#.#...#.#...

Sample Output 3

Yes



Sample input:
7 1 3 6 7
.#..#..


Sample output:
Yes

Submission status: Wrong Answer

Solution code:
n, a, b, c, d = map(int, input().split())
s = input()
flag = True
for i in range(a - 1, max(c, d) - 2):
    if s[i:i+2] == "##":
        flag = False
        break
if flag == False:
    print("No")
else:
    if c < d:
        print("Yes")
    else:
        flag2 = False
        for i in range(b - 1, min(c, d) - 3):
            if s[i:i+3] == "...":
                flag2 = True
                break
        if flag2 == True:
            print("Yes")
        else:
            print("No")

Submission status: Wrong Answer

Solution code:
from sys import exit, setrecursionlimit, stderr, stdin
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect
import functools

setrecursionlimit(10**7)

def input():
  return stdin.readline().strip()

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N, A, B, C, D = reads()
S = input()

def reachable(i, j):
  return not any(S[k] == S[k+1] == "#" for k in range(i, j))

def swappable(i, j):
  return any(S[k] == S[k+1] == S[k+2] == "." for k in range(i, j-1))

A, B, C, D = A-1, B-1, C-1, D-1

possible = reachable(A, C) and reachable(B, D)

if D < C:
  possible = possible and swappable(A, C)

print("Yes" if possible else "No")

Submission status: Wrong Answer

Solution code:
n, a, b, c, d = [int(i) for i in input().split()]
S = ' ' + input()

if '##' in S[a:c + 1]:
    print('No')
elif '##' in S[b:d + 1]:
    print('No')
else:
    if c < d:
        print('Yes')
    elif '...' in S[b:c + 1]:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq as hq
import itertools as its
import operator as op


# globals
inf = float('inf')
N = 0


def set_inputs():
    global N
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    n, a, b, c, d = get_li()
    s = get_str()
    if "##" in s[a:c]:
        print("No")
        return
    if "##" in s[b:d]:
        print("No")
        return
    if c > d and "..." not in s[b:d]:
        print("No")
        return
    print("Yes")
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, a, b, c, d = map(int, input().split())
s = input()

if s[c-1] == '#' or s[d-1] == '#' or c == d:
    print("No")
else:
    if c < d:
        if "##" not in s[:d-1]:
            print("Yes")
        else:
            print("No")
    else:
        if "..." in s[:c]:
            print("Yes")
        else:
            print("No")

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,a,b,c,d = li_()
n += 1
s = ns()


if c < d:
    if "xx" in s[a:c+1] or "xx" in s[b:d+1]:
        print("No")

    else:
        print("Yes")

else:
    if not "..." in s[b:d+1]:
        print("No")

    elif "xx" in s[a:c + 1] or "xx" in s[b:d + 1]:
        print("No")

    else:
        print("Yes")

Submission status: Wrong Answer

Solution code:
def main():
	n,a,b,c,d = map(int,input().split())
	s = input()
	ans = ""
	if c < d:
		if s.count("##",a, d) > 0:
			ans = "No"
		else:
			ans = "Yes"
	else:
		if s.count("##", a ,c) > 0 or s.count("...",b, d) == 0:
			ans = "No"
		else:
			ans = "Yes"
	print(ans)
	return
main()

Submission status: Wrong Answer

Solution code:
import queue

"""
N = int(input())
#S = input()
# (N,M) = (int(i) for i in input().split(" "))
# A = [int(i) for i in input().split()]
A = []
for i in range(N):
	A.append(int(input()))

print(A)

"""
(N,A,B,C,D) = (int(i) for i in input().split(" "))
S = input()

if "##" in S[A-1:max(C,D)]:
	print("No")
else:
	if C < D:
		print("Yes")
	else:
		if "..." in S[B-1:D]:
			print("Yes")
		else:
			print("No")

Submission status: Wrong Answer

Solution code:
import sys
n, a, b, c, d = map(int, input().split())
s = input()
snuke, fnuke, gnuke = 0, 0, 0
s_max, f_max, g_max = 0, 0, 0
for i in range(a-1, c):
	if s[i] == "#":
		snuke += 1
		s_max = max(s_max, snuke)
	else:
		snuke = 0
for i in range(b-1, d):
	if s[i] == "#":
		fnuke += 1
		f_max = max(f_max, fnuke)
		gnuke = 0
	else:
		fnuke = 0
		gnuke += 1
		g_max = max(g_max, gnuke)

if s_max > 1 or f_max > 1:
	print("No")
elif c < d:
	print("Yes")
else:
	if g_max >= 3:
		print("Yes")
	else:
		print("No")

Submission status: Wrong Answer

Solution code:
N, A, B, C, D = map(int, raw_input().split())
A -= 1
B -= 1
C -= 1
D -= 1
S = raw_input()

f1 = True
for i in range(A, C-1):
  if S[i]=="#" and S[i+1]=="#":
    f1 = False

f2 = True
for i in range(B, D-1):
  if S[i]=="#" and S[i+1]=="#":
    f2 = False

f3 = False
for i in range(B-1, D-2):
  if S[i]=="." and S[i+1]=="." and S[i+2]==".":
    f3 = True

if f1 and f2 and (C<D or f3):
  print "Yes"
else:
  print "No"

Submission status: Wrong Answer

Solution code:
n, a, b, c, d = map(int, input().split())
s = input()

if s[c-1] == '#' or s[d-1] == '#' or c == d:
    print("No")
else:
    if c < d:
        if "##" not in s[:d-1]:
            print("Yes")
        else:
            print("No")
    else:
        if "..." in s[:c-1]:
            print("Yes")
        else:
            print("No")

Submission status: Wrong Answer

Solution code:
n,a,b,c,d = map(int, input().split())
s = input()

if '##' in s[b:d+1]:
    print('No')
    exit()
if '##' in s[a:c+1]:
    print('No')
    exit()

if d < c:
    if '...' not in s[b:d+1]:
        print('No')
        exit()
print('Yes')

Submission status: Wrong Answer

Solution code:
from sys import exit, setrecursionlimit, stderr, stdin
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect
import functools

setrecursionlimit(10**7)

def input():
  return stdin.readline().strip()

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N, A, B, C, D = reads()
S = input()

def reachable(i, j):
  return not any(S[k] == S[k+1] == "#" for k in range(i, j))

def swappable(i, j):
  return any(S[k] == S[k+1] == S[k+2] == "." for k in range(i, j-1))

A, B, C, D = A-1, B-1, C-1, D-1


if C < D:
  possible = reachable(A, D)
else:
  possible = reachable(A, C) and swappable(A, C)

print("Yes" if possible else "No")

Submission status: Wrong Answer

Solution code:
n, a, b, c, d = [int(i) for i in input().split()]
S = ' ' + input()

if '##' in S[a:c + 1]:
    print('No')
elif '##' in S[b:d + 1]:
    print('No')
else:
    if c < d:
        print('Yes')
    elif '...' in S[a:c + 1]:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

Solution code:
def solve(a, b, c, d, s):
    a -= 1
    b -= 1
    c -= 1
    d -= 1
    ss = s[a:c + 1]
    fs = s[b:d + 1]
    if '##' in ss or '##' in fs:
        return False

    if c < d:
        return True

    if '...' in ss and '...' in fs:
        return True

    return False


n, a, b, c, d = list(map(int, input().split()))
s = input()
print('Yes' if solve(a, b, c, d, s) else 'No')

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)


def main():
    n,a,b,c,d = LI_()
    n += 1
    s = S()
    if d < c:
        f = 0
        for i in range(max(0,b-1), min(n-1,d+1)):
            if s[i:i+3] == '...':
                f = 1
                break
        if f == 0:
            return 'No'

    for i in range(a+1,c-1):
        if s[i:i+2] == '##':
            return 'No'
    for i in range(b+1,d-1):
        if s[i:i+2] == '##':
            return 'No'


    return 'Yes'


print(main())

Submission status: Wrong Answer

Solution code:
N,A,B,C,D=map(int,input().split())
S=input()
A-=1
B-=1
C-=1
D-=1
if "##" in S[A:C+1] or "##" in S[B:D+1]:
    print('No')
else:
    if C<D:
        print('Yes')
    else:
        if "..." in S[B:D+1]:
            print('Yes')
        else:
            print('No')

Submission status: Wrong Answer

Solution code:
N, A, B, C, D = map(int, raw_input().split())
A -= 1
B -= 1
C -= 1
D -= 1
S = raw_input()

f1 = True
for i in range(A, max(C, D)-1):
  if S[i]=="#" and S[i+1]=="#":
    f1 = False

f2 = False
for i in range(B-1, D-2):
  if S[i]=="." and S[i+1]=="." and S[i+2]==".":
    f2 = True

if f1 and (C<D or f2):
  print "Yes"
else:
  print "No"

Submission status: Wrong Answer

Solution code:
def solve(a, b, c, d, s):
    a -= 1
    b -= 1
    c -= 1
    d -= 1
    ss = s[a:c + 1]
    fs = s[b:d + 1]
    if '##' in ss or '##' in fs:
        return False

    if c < d:
        return True

    if '...' in ss:
        return True

    return False


n, a, b, c, d = list(map(int, input().split()))
s = input()
print('Yes' if solve(a, b, c, d, s) else 'No')

Submission status: Wrong Answer

Solution code:
print("I don't know")

Submission status: Wrong Answer

Solution code:
print("わからないよー")

Submission status: Time Limit Exceeded

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

N,A,B,C,D=map(int,input().split())
S="*"+input()

M={(C,D):True}

def f(X,Y):
    if (X,Y) in M:
        return M[(X,Y)]

    if C<X or D<Y:
        return False

    F=False
    try:
        if S[X+1]=="." and Y!=X+1:
            F|=f(X+1,Y)
    except:
        pass
    
    try:
        if S[X+2]=="." and Y!=X+2:
            F|=f(X+2,Y)
    except:
        pass

    try:
        if S[Y+1]=="." and X!=Y+1:
            F|=f(X,Y+1)
    except:
        pass
    
    try:
        if S[Y+2]=="." and X!=Y+2:
            F|=f(X,Y+2)
    except:
        pass

    M[(X,Y)]=F
    return F

if f(A,B):
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
n,a,b,c,d = map(lambda x:int(x)-1,input().split())
n+=1
s = input()

import sys
sys.setrecursionlimit(10**8)

def solve(a,b,c,d):
    if a==c and b==d:
        print('Yes')
        sys.exit()
    elif a>c or b>d:
        return
    else:
        if a+1<n:
            if s[a+1]=='.' and a+1!=b:
                solve(a+1,b,c,d)
        if a+2<n:
            if s[a+2]=='.' and a+2!=b:
                solve(a+2,b,c,d)
        if b+1<n:
            if s[b+1]=='.' and a!=b+1:
                solve(a,b+1,c,d)
        if b+2<n:
            if s[b+2]=='.' and a!=b+2:
                solve(a,b+2,c,d)
solve(a,b,c,d)
print('No')

Submission status: Time Limit Exceeded

Solution code:
n,a,b,c,d = map(lambda x:int(x)-1,input().split())
n+=1
s = input()

import sys
sys.setrecursionlimit(10**8)

def solve(a,b,c,d):
    if a==c and b==d:
        print('Yes')
        sys.exit()
    elif a>c or b>d:
        return
    else:
        if a+1<len(s):
            if s[a+1]=='.' and a+1!=b:
                solve(a+1,b,c,d)
        if a+2<len(s):
            if s[a+2]=='.' and a+2!=b:
                solve(a+2,b,c,d)
        if b+1<len(s):
            if s[b+1]=='.' and a!=b+1:
                solve(a,b+1,c,d)
        if b+2<len(s):
            if s[b+2]=='.' and a!=b+2:
                solve(a,b+2,c,d)
solve(a,b,c,d)
print('No')

Submission status: Time Limit Exceeded

Solution code:
import sys
n, a, b, c, d = map(int, sys.stdin.readline().split())
s = sys.stdin.readline().rstrip()

dp = [[False for _ in range(n)] for _ in range(n)]
dp[a-1][b-1] = True

for i in range(a-1, n):
    for j in range(b-1, n):
        if i == j: continue
        if not dp[i][j]: continue
        for x, y in ((1, 0), (2, 0), (0, 1), (0, 2)):
            if (i+x < n) and (j+y < n) and s[i+x] == '.' and s[j+y] == '.':
                dp[i+x][j+y] = True

print('Yes' if dp[c-1][d-1] else 'No')

Submission status: Time Limit Exceeded

Solution code:
n,a,b,c,d = map(int,input().split())
s = input()
ng = '##'
if c < d:
    rt1 = s[a-1:c]
    rt2 = s[b-1:d]
    if (ng not in rt1) and (ng not in rt2):
        print('Yes')
    else:
        print('No')
else:
    rt2 = s[b-1:d]
    if ng in rt2:
        print('No')
    else:
        for i in range(b-1, d):
            if s[i] != '#':
                tmp_s = s[:i]+'#'+s[i+1:]
                rt1 = tmp_s[a-1:c]
                if ng not in rt1:
                    print('Yes')
                    exit()
        print('No')

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(100000)
input = sys.stdin.readline

N, A, B, C, D = list(map(int, input().split()))
S = input()

def able(m, n, S):
    for i in range(m+1, n):
        if S[i] == '#' and S[i+1] == '#':
            return False
    return True

def able2(m, n, S):
    for i in range(m, n):
        if not able(m, n, S):
            return False
        if S[i] == '.' and S[i-1] == '.' and S[i+1] == '.':
            return True
    return False

if C>D:
    if able(A-1, C-1, S) and able2(B-1, D-1, S):
        print("Yes")
    else:
        print("No")
else:
    if able(A-1, C-1, S) and able(B-1, D-1, S):
        print("Yes")
    else:
        print("No")

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
import bisect
from collections import defaultdict
import math

def judge(start, end, S):
    for i in range(start, end):
        s = S[i:i+2]
        if tuple(s) == ("#", "#"):
            return False
    return True

def main():
    N, A, B, C, D = map(int, input().split())
    S = list(input().strip())

    is_ok = judge(A-1, C-1, S)
    if not is_ok:
        print("No")
        return
    is_ok = judge(B-1, D-1, S)
    if not is_ok:
        print("No")
        return

    if C > D:
        for i in range(B-1, D):
            if S[i] != "#":
                new_S = list(S)
                new_S[i] = "#"
                is_ok = judge(A-1, C-1, new_S)
                if is_ok:
                    print("Yes")
                    return
        print("No")
    else:
        print("Yes")

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,A,B,C,D=map(int,input().split())
S=list(input())
mass=[]
for i in range(N):
  if S[i] !='#':
  	mass.append(i+1)
An = A
Bn = B
M = 0
while (An < C or Bn < D) and M == 0: 
  if An + 1 <= C and An+1 in mass and An+1 != Bn:
  	An += 1
  elif An + 2 <= C and An+2 in mass and An+2 != Bn:
  	An += 2
  elif Bn + 1 <= D and Bn+1 in mass and Bn+1 != An:
  	Bn += 1
  elif Bn + 2 <= D and Bn+2 in mass and Bn+2 != An:
  	Bn += 2
  else:
    M = 1
if M==0 and An == C and Bn == D: 
  print ('Yes')
else:
  print('No')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, A, B, C, D = map(int, input().split(" "))
A -= 1
B -= 1
C -= 1
D -= 1
S = input()

s = deque()
s.append((A, B))
r = False

def canMove(f, step, o):
    return f + step < len(S) and f + step != o and S[f + step] == '.'

canGo = {}

while s:
    a, b = s.pop()
    if (a, b) in canGo:
        continue

    # SS = list(S)
    # SS[a] = 'A'
    # SS[b] = 'B'
    # print(''.join(SS))
    if a == C and b == D:
        r = True
        break

    if b < D:
        can1 = canMove(b, 1, a)
        can2 = canMove(b, 2, a)
        if not can1 and not can2 and a == C:
            # print("Can go no more", a, b, ''.join(SS))
            canGo[(a, b)] = False
            continue

        if b + 1 <= D and can1 and (a, b + 1) not in canGo:
            s.append((a, b + 1))
            can = True
        if b + 2 <= D and can2 and (a, b + 2) not in canGo:
            s.append((a, b + 2))
            can = True
        if not can:
            canGo[(a, b)] = False
            continue

    if a < C:
        can1 = canMove(a, 1, b)
        can2 = canMove(a, 2, b)
        if not can1 and not can2 and b == D:
            # print("Can go no more", a, b, ''.join(SS))
            canGo[(a, b)] = False
            continue

        can = False
        if a + 1 <= C and can1 and (a + 1, b) not in canGo:
            s.append((a + 1, b))
            can = True
        if a + 2 <= C and can2 and (a + 2, b) not in canGo:
            s.append((a + 2, b))
            can = True
        if not can:
            canGo[(a, b)] = False
            continue

if r:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, A, B, C, D = map(int, input().split(" "))
A -= 1
B -= 1
C -= 1
D -= 1
S = input()

# canGo = {}

# canGo[(C, D)] = True
# canGo[(C - 1, D)] = S[C - 1] == '.' and D != C - 1
# canGo[(C - 2, D)] = S[C - 2] == '.' and D != C - 2

# canGo[(C, D - 1)] = S[D - 1] == '.' and C != D - 1
# canGo[(C, D - 2)] = S[D - 2] == '.' and C != D - 2

# for i in reversed(range(C)):
#     for j in reversed(range(D)):
#         print(i, j)
#         c = [
#             canGo[(i + 1, j)],
#             canGo[(i, j + 1)]
#         ]
#         if i < C - 1:
#             c.append(canGo[(i + 2, j)])
#         if j < D - 1:
#             c.append(canGo[(i, j + 2)])

#         cg = S[i] == '.' and S[j] == '.' and any(c)
#         canGo[(i, j)] = cg

s = deque()
s.append((A, B))
r = False
# print(A, "to", C)
# print(B, "to", D)

def canMove(f, step, o):
    return f + step < len(S) and f + step != o and S[f + step] == '.'

canGo = {}

while s:
    a, b = s.pop()
    if (a, b) in canGo:
        # print("Hey")
        continue

    # SS = list(S)
    # SS[a] = 'A'
    # SS[b] = 'B'
    # print(''.join(SS))
    if a == C and b == D:
        r = True
        break

    if b < D:
        can1 = canMove(b, 1, a)
        can2 = canMove(b, 2, a)
        if not can1 and not can2 and a == C:
            # print("Can go no more", a, b, ''.join(SS))
            canGo[(a, b)] = False
            continue

        if b + 1 <= D and can1 and (a, b + 1) not in canGo:
            s.append((a, b + 1))
            can = True
        if b + 2 <= D and can2 and (a, b + 2) not in canGo:
            s.append((a, b + 2))
            can = True
        if not can:
            canGo[(a, b)] = False
            continue

    if a < C:
        can1 = canMove(a, 1, b)
        can2 = canMove(a, 2, b)
        if not can1 and not can2 and b == D:
            # print("Can go no more", a, b, ''.join(SS))
            canGo[(a, b)] = False
            continue

        can = False
        if a + 1 <= C and can1:
            s.append((a + 1, b))
            can = True
        if a + 2 <= C and can2:
            s.append((a + 2, b))
            can = True
        if not can:
            canGo[(a, b)] = False
            continue

if r:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, A, B, C, D = map(int, input().split(" "))
A -= 1
B -= 1
C -= 1
D -= 1
S = input()

# canGo = {}

# canGo[(C, D)] = True
# canGo[(C - 1, D)] = S[C - 1] == '.' and D != C - 1
# canGo[(C - 2, D)] = S[C - 2] == '.' and D != C - 2

# canGo[(C, D - 1)] = S[D - 1] == '.' and C != D - 1
# canGo[(C, D - 2)] = S[D - 2] == '.' and C != D - 2

# for i in reversed(range(C)):
#     for j in reversed(range(D)):
#         print(i, j)
#         c = [
#             canGo[(i + 1, j)],
#             canGo[(i, j + 1)]
#         ]
#         if i < C - 1:
#             c.append(canGo[(i + 2, j)])
#         if j < D - 1:
#             c.append(canGo[(i, j + 2)])

#         cg = S[i] == '.' and S[j] == '.' and any(c)
#         canGo[(i, j)] = cg

s = deque()
s.append((A, B))
r = False
# print(A, "to", C)
# print(B, "to", D)

def canMove(f, step, o):
    return f + step < len(S) and f + step != o and S[f + step] == '.'

while s:
    a, b = s.pop()
    # SS = list(S)
    # SS[a] = 'A'
    # SS[b] = 'B'
    # print(''.join(SS))
    if a == C and b == D:
        r = True
        break
    if b < D:
        if b + 1 <= D and canMove(b, 1, a):
            s.append((a, b + 1))
        if b + 2 <= D and canMove(b, 2, a):
            s.append((a, b + 2))
    if a < C:
        if a + 1 <= C and canMove(a, 1, b):
            s.append((a + 1, b))
        if a + 2 <= C and canMove(a, 2, b):
            s.append((a + 2, b))

if r:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
n, a, b, c, d = list(map(int, input().split()))
s = input()
position = [[0]*(n+1) for _ in range(n+1)]
position[a][b] = 1

def move(x,y):
    if x < a or y < b:
        return 0
    if x == y:
        return 0
    if s[x-1] == '#' or s[y-1] == '#':
        return 0
    if position[x][y] == 1:
        return position[x][y]
    position[x][y] = move(x-1,y) or move(x-2,y) or move(x,y-1) or move(x,y-2)
    return position[x][y]

print('Yes' if move(c,d) == 1 else 'No')

Submission status: Time Limit Exceeded

Solution code:
class Kenken():
	def __init__(self,n,a,b,c,d,s):
		self.n = n
		self.a = a-1
		self.b = b-1
		self.c = c-1
		self.d = d-1
		self.s = s
		self.s = self.s[:a-1] + "A" + self.s[a:]
		self.s = self.s[:b-1] + "B" + self.s[b:]

	def str_replace(self,i,k,S):
		if k == 1:
			self.s = self.s[:i] + "." + S + self.s[i+2:]
		else:
			self.s = self.s[:i] + "." + self.s[i+1] + S + self.s[i+3:]

	def check_stone(self,i):
		if i < self.n:
			if self.s[i] == ".":
				return True
		return False

	def check_goal(self):
		if self.a == self.c and self.b == self.d:
			return False
		else:
			return True

	def left(self,target,i):
		if target == "a":
			self.str_replace(self.a,i,"A")
			self.a += i
		else:
			self.str_replace(self.b,i,"B")
			self.b += i
	
	def get_space(self,S):
		if S == "a":
			return self.a
		elif S == "b":
			return self.b
		elif S == "c":
			return self.c
		elif S == "d":
			return self.d

	def print_all(self):
		print(self.s)

n,a,b,c,d = map(int, input().split())
s = input()

if c > d:
	if s.find("...") == -1:
		print("No")
		exit()
ken = Kenken(n,a,b,c,d,s)
flag=0
while ken.check_goal():
	if (ken.check_stone(ken.get_space("b")+1) and ken.check_stone(ken.get_space("b")-1)) or (ken.get_space("a")+1 == ken.get_space("b") and ken.check_stone(ken.get_space("b")+1)): 
		if ken.check_stone(ken.get_space("a")+1) and ken.get_space("a") != ken.get_space("c"):
			ken.left("a",1)
		elif ken.check_stone(ken.get_space("a")+2) and ken.get_space("a") != ken.get_space("c"):
			ken.left("a",2)
		elif ken.check_stone(ken.get_space("b")+1) and ken.get_space("b") != ken.get_space("d"):
			ken.left("b",1)
		elif ken.check_stone(ken.get_space("b")+2) and ken.get_space("b") != ken.get_space("d"):
			ken.left("b",2)
		else:
			flag=1
			break
	else:
		if ken.check_stone(ken.get_space("b")+1) and ken.get_space("b") != ken.get_space("d"):
			ken.left("b",1)
		elif ken.check_stone(ken.get_space("b")+2) and ken.get_space("b") != ken.get_space("d"):
			ken.left("b",2)
		elif ken.check_stone(ken.get_space("a")+1) and ken.get_space("a") != ken.get_space("c"):
			ken.left("a",1)
		elif ken.check_stone(ken.get_space("a")+2) and ken.get_space("a") != ken.get_space("c"):
			ken.left("a",2)
		else:
			flag=1
			break

if flag == 0:
	print("Yes")
else:
	print("No")

Submission status: Time Limit Exceeded

Solution code:
n, a, b, c, d = list(map(int, input().split()))
s = input()
position = [[0]*(n+1) for _ in range(n+1)]
position[a][b] = 1

def move(x,y):
    if x < a or y < b:
        return 0
    if x == y:
        return 0
    if s[x-1] == '#' or s[y-1] == '#':
        return 0
    if position[x][y] == 1:
        return position[x][y]
    position[x][y] = move(x-1,y) or move(x-2,y) or move(x,y-1) or move(x,y-2)
    return position[x][y]

print('Yes' if move(c,d) == 1 else 'No')

Submission status: Time Limit Exceeded

Solution code:
class Kenken():
	def __init__(self,n,a,b,c,d,s):
		self.n = n
		self.a = a-1
		self.b = b-1
		self.c = c-1
		self.d = d-1
		self.s = s
		self.s = self.s[:a-1] + "A" + self.s[a:]
		self.s = self.s[:b-1] + "B" + self.s[b:]

	def str_replace(self,i,k,S):
		if k == 1:
			self.s = self.s[:i] + "." + S + self.s[i+2:]
		else:
			self.s = self.s[:i] + "." + self.s[i+1] + S + self.s[i+3:]

	def check_stone(self,i):
		if i < self.n:
			if self.s[i] == ".":
				return True
		return False

	def check_goal(self):
		if self.a == self.c and self.b == self.d:
			return False
		else:
			return True

	def left(self,target,i):
		if target == "a":
			self.str_replace(self.a,i,"A")
			self.a += i
		else:
			self.str_replace(self.b,i,"B")
			self.b += i
	
	def get_space(self,S):
		if S == "a":
			return self.a
		elif S == "b":
			return self.b
		elif S == "c":
			return self.c
		elif S == "d":
			return self.d

	def print_all(self):
		print(self.s)

n,a,b,c,d = map(int, input().split())
s = input()

ken = Kenken(n,a,b,c,d,s)
flag=0
while ken.check_goal():
	if (ken.check_stone(ken.get_space("b")+1) and ken.check_stone(ken.get_space("b")-1)) or (ken.get_space("a")+1 == ken.get_space("b") and ken.check_stone(ken.get_space("b")+1)): 
		if ken.check_stone(ken.get_space("a")+1) and ken.get_space("a") != ken.get_space("c"):
			ken.left("a",1)
		elif ken.check_stone(ken.get_space("a")+2) and ken.get_space("a") != ken.get_space("c"):
			ken.left("a",2)
		elif ken.check_stone(ken.get_space("b")+1) and ken.get_space("b") != ken.get_space("d"):
			ken.left("b",1)
		elif ken.check_stone(ken.get_space("b")+2) and ken.get_space("b") != ken.get_space("d"):
			ken.left("b",2)
		else:
			flag=1
			break
	else:
		if ken.check_stone(ken.get_space("b")+1) and ken.get_space("b") != ken.get_space("d"):
			ken.left("b",1)
		elif ken.check_stone(ken.get_space("b")+2) and ken.get_space("b") != ken.get_space("d"):
			ken.left("b",2)
		elif ken.check_stone(ken.get_space("a")+1) and ken.get_space("a") != ken.get_space("c"):
			ken.left("a",1)
		elif ken.check_stone(ken.get_space("a")+2) and ken.get_space("a") != ken.get_space("c"):
			ken.left("a",2)
		else:
			flag=1
			break

if flag == 0:
	print("Yes")
else:
	print("No")

Submission status: Time Limit Exceeded

Solution code:
class Kenken():
	def __init__(self,n,a,b,c,d,s):
		self.n = n
		self.a = a-1
		self.b = b-1
		self.c = c-1
		self.d = d-1
		self.s = s
		self.s = self.s[:a-1] + "A" + self.s[a:]
		self.s = self.s[:b-1] + "B" + self.s[b:]

	def str_replace(self,i,k,S):
		if k == 1:
			self.s = self.s[:i] + "." + S + self.s[i+2:]
		else:
			self.s = self.s[:i] + "." + self.s[i+1] + S + self.s[i+3:]

	def check_stone(self,i):
		if i < self.n:
			if self.s[i] == ".":
				return True
		return False

	def check_goal(self):
		if self.a == self.c and self.b == self.d:
			return False
		else:
			return True

	def left(self,target,i):
		if target == "a":
			self.str_replace(self.a,i,"A")
			self.a += i
		else:
			self.str_replace(self.b,i,"B")
			self.b += i
	
	def get_space(self,S):
		if S == "a":
			return self.a
		elif S == "b":
			return self.b
		elif S == "c":
			return self.c
		elif S == "d":
			return self.d

n,a,b,c,d = map(int, input().split())
s = input()

ken = Kenken(n,a,b,c,d,s)
flag=0
while ken.check_goal():
	if (ken.check_stone(ken.get_space("b")+1) and ken.check_stone(ken.get_space("b")-1)) or (ken.get_space("a")+1 == ken.get_space("b") and ken.check_stone(ken.get_space("b")+1)): 
		if ken.check_stone(ken.get_space("a")+1) and ken.get_space("a") != ken.get_space("c"):
			ken.left("a",1)
		elif ken.check_stone(ken.get_space("a")+2) and ken.get_space("a") != ken.get_space("c"):
			ken.left("a",2)
		elif ken.check_stone(ken.get_space("b")+1) and ken.get_space("b") != ken.get_space("d"):
			ken.left("b",1)
		elif ken.check_stone(ken.get_space("b")+2) and ken.get_space("b") != ken.get_space("d"):
			ken.left("b",2)
		else:
			flag=1
			break
	else:
		if ken.check_stone(ken.get_space("b")+1) and ken.get_space("b") != ken.get_space("d"):
			ken.left("b",1)
		elif ken.check_stone(ken.get_space("b")+2) and ken.get_space("b") != ken.get_space("d"):
			ken.left("b",2)
		elif ken.check_stone(ken.get_space("a")+1) and ken.get_space("a") != ken.get_space("c"):
			ken.left("a",1)
		elif ken.check_stone(ken.get_space("a")+2) and ken.get_space("a") != ken.get_space("c"):
			ken.left("a",2)
		else:
			flag=1
			break

if flag == 0:
	print("Yes")
else:
	print("No")