算法思路

• s[N][N] 存储图,如果s[1][1]==’)’提前结束，因为题目要求路径为(((…)))这种格式

• st[N][N]记录走过的路径

• 一般来说，捡马蹄的方式为先捡 ( ,如果捡了 ) 那么之后就只能捡 ) ,直到 ( 的数目和 ) 的数目一样多。

• dfs(x,y,l,r) ==> x,y为当前位置 , L 为已经捡了L个’（‘型马蹄铁，R为已经捡了R个’）‘型马蹄铁

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N= 10;
char s[N][N];
int n;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
bool st[N][N];
int ans=0;
void dfs(int x,int y,int l,int r)
{

    if(l>0&&l==r)
    {
        ans=max(ans,l+r);
        return ;
    }
        for(int i=0;i<4;i++)
        {
            int xx=x+dx[i],yy=y+dy[i];
            if(xx<1||yy<1||xx>n||yy>n||st[xx][yy])continue;

            if(r>0&&s[xx][yy]=='(')
            {
                continue;
            }

            st[xx][yy]=true;

            if(s[xx][yy]=='(')dfs(xx,yy,l+1,r);
            else dfs(xx,yy,l,r+1);

            st[xx][yy]=false;//回溯

        }

    return ;

}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s[i]+1);
    }
    if(s[1][1]==')')
    {
        puts("0");
        return 0;
    }
    st[1][1]=true;
    dfs(1,1,1,0);
    cout<<ans<<endl;
    return 0;
}