Submission #43122573

---

Source Code Expand

H, W = map(int, input().split(' '))
v = []
for i in range(H):
    line = input()
    v.append(list(line))

s = "snuke"

def main():
    candidate = set([(0, 0)])
    if v[0][0] != 's':
        return False
    for i in range(1, H * W):
        if len(candidate) < 1:
            return False

        candidate = step(candidate, i)
        # print(s[i % 5], i, candidate)
        if (H-1, W-1) in candidate:
            return True
    if (H - 1, W - 1) in candidate:
        return True
    return False

def step(candidate, i):
    char = s[i % 5]
    new_candidate = set()
    for y, x in candidate:
        for y1, x1 in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            yy = y + y1
            xx = x + x1
            if 0 <= yy < H and 0 <= xx < W:
                # print(yy, xx)
                if v[yy][xx] == char:
                    new_candidate.add((yy, xx))
    return new_candidate

if main():
    print('Yes')
else:
    print('No')

Submission Info

Judge Result