AcWing 2005.马蹄铁 （DFS）

题目链接

https://www.acwing.com/problem/content/2007/

思路

dfs,维护两个变量，记录左右括号的数量即可。

AC代码

#include 
#include 
#include 
using namespace std;
const int N = 6;
int n;
char map[N][N];
int ans = 0;
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };
bool visited[N][N];
void dfs(int x,int y,int l,int r)
{
	visited[x][y] = true;
	if(l==r)
	{
		ans = max(ans, l + r);//如果左右括号一样多则取一次答案
		visited[x][y] = false;
		return;
	}
	for(int i=0;i<4;i++)
	{
		int a = dx[i] + x;
		int b = dy[i] + y;

		if(a>=0&&a=0&&b> n;

	for(int i=0;i> map[i][j];
		}
	}
	if (map[0][0] == ')')//如果一开始就是右括号则无答案
		cout << 0;
	else
	{
		dfs(0, 0, 1, 0);//从第一个点开始搜
		cout << ans;
	}
	
}

心得

本来维护了一个栈来写，结果错了，不知道错在哪，这个思路是copy的，不过很巧妙，直接抽象化了。
题目好像没我想的复杂，不用判断合法与否