博客

原题链接：

2005. 马蹄铁 – AcWing题库


高质量的算法题库



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

思路：

直接dfs暴力枚举所有路径然后求最大值就行，唯一麻烦一点的地方就是还得写个check函数判断一下路径是否合法，这题数据范围小，就是练暴力用的，具体细节见代码

Code：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10;
int ans;
int X,Y;
bool st[N][N];
int num[N*N*N];
char g[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n;
int res=1;
bool check()
{
    if(res%2) return false;

    for(int i=0;i<res/2;i++)
    {
        if(num[i]!=1) return false;
    }

    for(int i=res-1;i>=res/2;i--)
    if(num[i]!=2) return false;

    return true;
}

void dfs(int x,int y)
{
    if(x==X&&y==Y)
    {
        if(check())
        {
            ans=max(ans,res);
        }
        return;
    }

    for(int i=0;i<4;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(st[a][b]||a<0||b<0||a>=n||b>=n) continue;
        st[a][b]=true;
        //cout<<a<<" "<<b<<endl;
        if(g[a][b]=='(') num[res]=1;
        else
        num[res]=2;
        res++;
 
        dfs(a,b);
        res--;
        st[a][b]=false;
        num[res]=0;

    }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>g[i][j];

    if(g[0][0]=='(') num[0]=1;
    else
    num[0]=2;

    st[0][0]=true;

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            X=i,Y=j;
            dfs(0,0);
        }
    }

    cout<<ans<<endl;
    return 0;
}

作者：机械之忍

链接：https://www.acwing.com/activity/content/code/content/2257351/

来源：AcWing

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。