119 周赛 —— 有好题

第一题和第二题略，有时候我真的感觉一二题是拿来凑数的。

第三题虽然没做出来，但我认为是道好题，因为我居然直到最后一分钟才想到 DFS。虽然想到了，但也没法马上解决。

这个题解不错，他说出了我没想到的关键点——保留前一个位置。

【改写题解代码】

n, m = map(int, input().strip().split())
matrix = [input() for _ in range(n)]
# n,m = 3, 4
# matrix = [
#     'DDDD',
#     'DBCD',
#     'DDDD',]

"""
下一个点的要求：
    1. 只能是上下左右
    2. 位置不越界
    3. 不是前一个位置
    4. 颜色相同
"""
def get_next(x, y, prev_x, prev_y):
    tmp = [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]
    res = []
    for nx, ny in tmp:
        if nx == prev_x and ny == prev_y:
            continue
        if 0<=nx<n and 0<=ny<m and matrix[x][y] == matrix[nx][ny]:
            res.append([nx, ny])
    return res

def dfs(x, y, prev_x, prev_y, steps, visited):
    visited[x][y] = True
    steps += 1
    nextXY = get_next(x, y, prev_x, prev_y)
    for nx, ny in nextXY:
        if visited[nx][ny] and steps >= 4:
            return True
        elif not visited[nx][ny]:
            if dfs(nx, ny, x, y, steps, visited):
                return True
    return False

def resolve():
    visited = [[False] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if not visited[i][j] and dfs(i, j, -1, -1, 0, visited):
                print("Yes")
                return
    print("No")

resolve()