本文主要是介绍AcWing 2005. 马蹄铁（DFS），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目链接

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

思路

由于这个题目数据范围很小，所以我们可以进行暴力搜索，从左上角1，1点开始回溯搜索，注意的是，由于要形成题目中括号的格式，所以我们能发现左括号能走到左括号或者右括号，而右括号只能走到右括号

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000009
ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 10;
int n;

char mp[N][N];
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
bool check(int x,int y){
	if(x >= 1 && x <= n && y >= 1 && y<= n) {
		return true;
	}
	return false;
}
bool vis[N][N];
int ans = 0;
map<string,bool> viss;

bool is_ok(string ch){//判断是否为正确的括号序列
	int len = ch.size();
	if(len % 2) return false;
	for(int i = 0;i < len/2; ++i) {
		if(ch[i] =='(' && ch[len-i-1] == ')') continue;
		return false;
	}
	return true;
}

void dfs(int x,int y,string ch){//回溯暴力搜索
	if(is_ok(ch)){
//		puts("-----begin-----");
//		cout<<ch<<endl;
//		puts("-----end-----");
		ans = max(ans,(int)ch.length());
		return;
	}
	for(int i = 0;i < 4; ++i) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if(check(nx,ny) && vis[nx][ny] == false) {
			if(mp[x][y] == '('){//左括号可以到右括号，也可以到左括号
				vis[nx][ny] = true;
				ch.push_back(mp[nx][ny]);
				dfs(nx,ny,ch);
				vis[nx][ny] = false;
				ch.pop_back();
			}
			else{
				if(mp[nx][ny] == ')') {//右括号只能到左括号
					vis[nx][ny] = true;
					ch.push_back(mp[nx][ny]);
					dfs(nx,ny,ch);
					vis[nx][ny] = false;
					ch.pop_back();
				}
			}
		}
	}
}

int main()
{
	cin>>n;
	for(int i = 1;i <= n; ++i) {
		for(int j = 1;j <= n; ++j) {
			cin>>mp[i][j];
		}
	}
	string ch="";
	ch += mp[1][1];
	vis[1][1] = true;
	dfs(1,1,ch);
	cout<<ans<<endl;
	return 0;
}

这篇关于AcWing 2005. 马蹄铁（DFS）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！