AcWing 2005. 马蹄铁（DFS）

题目链接

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

思路

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

代码

#include
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 = 1 && y