C++14(g++5.4) 解法, 执行用时: 6ms, 内存消耗: 500K, 提交时间: 2020-08-18 21:17:54

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
const int N=200005;
int dir[4][2]={0,-1,0,1,-1,0,1,0};
int vis[6][6];
string s[6];
char c[30];
int n,ans;
void init()
{
    memset(vis,0,sizeof(vis));
    ans=0;
}
void dfs(int x,int y,int len)
{
    c[len]=s[x][y];
    vis[x][y]=1;
    if(len%2==0){
        int f=1;
        for(int i=1;i<=len/2;i++) if(c[i]!='(') f=0;
        for(int i=len/2+1;i<=len;i++) if(c[i]!=')') f=0;
        if(f) ans=max(ans,len);
    }
    for(int k=0;k<4;k++)
    {
        int X=x+dir[k][0],Y=y+dir[k][1];
        if(X<0||Y<0||X>=n||Y>=n) continue;
        if(!vis[X][Y])dfs(X,Y,len+1);
    }
    vis[x][y]=0;
}
int main()
{
    init();
    scanf("%d",&n);
    for(int i=0;i<n;i++) cin>>s[i];
    dfs(0,0,1);
    printf("%d\n",ans);
}

pypy3(pypy3.6.1) 解法, 执行用时: 406ms, 内存消耗: 26432K, 提交时间: 2020-07-03 19:09:05

#!/usr/bin/env python3
#
# Horseshoes
#
import sys, os

def read_int(): return int(input())
def read_str(): return input().strip()
#------------------------------------------------------------------------------#

n = read_int()
a = [read_str() for _ in range(n)]

def dfs(x, y, c1, c2, vi):
	global ans
	if a[x][y] == '(' and c2 > 0: return
	if a[x][y] == '(': c1 += 1
	else: c2 += 1
	if c2 > 0 and c1 <= ans // 2: return
	if c1 == c2: ans = max(ans, c1)
	vi[x][y] = True
	for xx, yy in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
		if 0 <= xx < n and 0 <= yy < n and not vi[xx][yy]:
			dfs(xx, yy, c1, c2, vi)
	vi[x][y] = False

ans = 0
vi = [[False] * n for _ in range(n)]

dfs(0, 0, 0, 0, vi)

print(ans * 2)

C++11(clang++ 3.9) 解法, 执行用时: 8ms, 内存消耗: 504K, 提交时间: 2020-07-03 20:45:19

#include<bits/stdc++.h>
using namespace std;

int dx[5]={0,0,1,-1};
int dy[5]={1,-1,0,0};

int n;

char s[9][9];

char t[109];
int vis[9][9];
int ans;
void check(int len){
	for(int i=1;i<=len/2;++i)if(t[i]!='(')return;
	for(int i=len/2+1;i<=len;++i)if(t[i]!=')')return;
	ans=max(ans,len);
}

void dfs(int x,int y,int len){
	t[len]=s[x][y];
	vis[x][y]=1;
	if(len%2==0)check(len);
	for(int k=0;k<4;++k){
		int xx=x+dx[k],yy=y+dy[k];
		if(xx<=0||yy<=0||xx>n||yy>n)continue;
		if(vis[xx][yy])continue;
		dfs(xx,yy,len+1);
	}
	vis[x][y]=0;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%s",s[i]+1);
	
	dfs(1,1,1);
	printf("%d\n",ans);
	return 0;
}