摘要
Title: 2005. 马蹄铁
Tag: DFS
Memory Limit: 64 MB
Time Limit: 1000 ms

2005. 马蹄铁

题意
思路

DFS爆搜即可，枚举每个状态，一种情况例外，即前一个状态为 $)$ ，后一个状态必须为 $)$

DFS回溯
- 标记状态
  在函数开始时标记即可，即在DFS状态前
- 回归状态
  - 在符合条件后return前回归状态
  - 在函数最后回归状态
总体来说在函数开始标记状态，在return前回归状态

代码

'''
Author: NEFU AB-IN
Date: 2022-02-11 14:28:34
FilePath: \ACM\Acwing\2005.py
LastEditTime: 2022-02-11 16:05:22
'''
import sys

sys.setrecursionlimit(10000000)

g = []
vis = [[0 for _ in range(5)] for _ in range(5)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

res = 0


def dfs(x, y, lnum, rnum, op):
    global res
    vis[x][y] = 1
    if op == '(':
        lnum += 1
    else:
        rnum += 1
    if lnum == rnum:
        res = max(res, lnum + rnum)
        vis[x][y] = 0
        return
    for i in range(4):
        a = x + dx[i]
        b = y + dy[i]
        if a >= 0 and a < n and b >= 0 and b < n and vis[a][b] == 0:
            if op == '(' or (op == ')' and g[a][b] == ')'):
                dfs(a, b, lnum, rnum, g[a][b])
    vis[x][y] = 0
    return


if __name__ == "__main__":
    n = int(input())
    for i in range(n):
        g.append(input())
    if g[0][0] == '(':
        dfs(0, 0, 0, 0, g[0][0])
    print(res)

2005. 马蹄铁

题意

思路

代码