【DFS】马蹄印(Horseshoes)

题目描述

虽然当奶牛贝里斯找到平衡序列后很高兴了，但是他现在对序列提出了一个更高的要求，就是要求每个序列中必须是先一定数量的左括号然后是与左括号相同数量的右括号。例如：（（（（）））），就是一个完美的平衡序列。
当贝里斯某天在农场上走的时候，他在地上发现了马蹄印，这个农场是一个N*N的方格，每个小方格中都有一个马蹄印。贝里斯希望从方格的最左上角的地方开始出发，然后每次可以向上或者向下或者向左或者向右移动一步，使得他走过的每个小方格中的马蹄印能够组成一个完美的平衡序列。当然了，贝里斯不能重复经过任何小方格。

问题描述：

请帮助贝里斯在这个N*N的方格中找出长度最长的完美序列的长度。

输入

第一行一个正整数N，表示农场的大小。
接下来N行，每行N个字符，表示N*N的方格上马蹄印的分布情况。

输出

只有一行一个整数，表示最长的完美序列的长度，如果不存在这样的完美序列（例如起始位置就是右括号），则输出0。

输入样例

4 
(()) 
()(( 
(()( 
)))) 

输出样例

8

说明

数据范围：2<=N<=5。
说明：样例中，奶牛的行走序列是这样的：
1())
2)((
345(
876)

思路

DFS搜

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
int F[25][25];
int Ans,n,m;
char s;
bool Check(int x,int y,int r,int c)
{
	if(x<1 || x>n || y<1 || y>n)return 0;
	if(F[x][y]==1 && r+1>(n*n+1)/2)return 0;
	if(F[x][y]==0 && r<c+1)return 0;
	if(F[x][y]==1 && c)return 0;//一堆优化
	if(F[x][y]==-1)return 0; 
	return 1;
}
void Dfs(int x,int y,int r,int c)
{
	if(r==c)
	{
		Ans=max(Ans,r+c);
		return;
	}
	for(int i=0;i<=3;++i)
		if(Check(x+dx[i],y+dy[i],r,c))
		{
			int m=F[x+dx[i]][y+dy[i]];
			F[x+dx[i]][y+dy[i]]=-1;
			if(m==1)r++;else if(m==0)c++;
			Dfs(x+dx[i],y+dy[i],r,c);
			F[x+dx[i]][y+dy[i]]=m;
			if(m==1)r--;else if(m==0)c--;
		}
}
int main()
{
	scanf("%d\n",&n);
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=n;++j)
		{
			s=getchar();
			if(s=='(')F[i][j]=1;
			else if(s==')')F[i][j]=0;
		}
		while(s!='\n')s=getchar();
	}
	if(F[1][1])//如果(1,1)为右括号就不用做了
	{
		F[1][1]=-1; 
		Dfs(1,1,1,0);
	}
	printf("%d",Ans);
	return 0;
}