(DFS search) acwing 2005 horseshoe

Add link description

DFS Explosive search

Key features of state transition ：

1. ( Can walk to ( or ) however ) We can only go to ), So the status of the last point should be recorded , So as to judge whether the current point can go
2. Update answers to meet ( The number of is equal to ) The number of , Therefore, record the explosive search

#include<iostream>
#include<algorithm>
using namespace std;
const int N=10;
char g[N][N];
bool st[N][N];
int n,ans;
int dx[]={
    0,1,0,-1},dy[]={
    1,0,-1,0};	
void dfs(int l,int r,int x,int y)	//f:0( f:1)
{
    
	st[x][y]=true;	// Note that it is marked in this position st, Because the first point should also be marked 
	
	if(l==r)
	{
    
		ans=max(l+r,ans);
		st[x][y]=false;		// Don't forget to restore the scene 
		return;
	}
	
	for(int i=0;i<4;i++)
	{
    
		int a=x+dx[i],b=y+dy[i];
		if(a<0||b<0||a>=n||b>=n||st[a][b]) continue;
		if(g[a][b]=='('&&g[x][y]==')') continue;
		
		if(g[a][b]==')') 	dfs(l,r+1,a,b);
		else dfs(l+1,r,a,b);
	}
	st[x][y]=false;
	
}
int main()
{
    
	cin>>n;
	for(int i=0;i<n;i++) cin>>g[i];
	
	if(g[0][0]=='(') dfs(1,0,0,0);
	
	cout<<ans<<endl;
	
	return 0;
}