[AGC039E] Pairing Points

#include <bits/stdc++.h>
typedef long long ll;
ll dp[40][40][40],ans;
int n,a[40][40];
char s[40];
ll dfs(int l,int r,int mid){
	if (l==r) return 1;
	if (r<l) return 0;
	if (l==mid || r==mid) return 0;
	if (dp[l][r][mid]!=-1) return dp[l][r][mid];
	dp[l][r][mid]=0;
	for (int i=l;i<mid;i++)
		for (int j=r;j>mid;j--){
			if (!a[i][j]) continue;
			for (int p1=i;p1<mid;p1++)
				for (int p2=j-1;p2>=mid;p2--)
					dp[l][r][mid]+=dfs(l,p1,i)*dfs(p1+1,p2,mid)*dfs(p2+1,r,j);
		}
	return dp[l][r][mid];
}
int main(){
	scanf("%d",&n);
	if (n==1){
		puts("1");
		return 0;
	} 
	for (int i=0;i<2*n;i++){
		scanf("%s",s);
		for (int j=0;j<2*n;j++)
			a[i][j]=s[j]-'0';
	}
	memset(dp,-1,sizeof(dp));
	for (int i=2;i<2*n-1;i++)
		if (a[0][i]) ans+=dfs(1,2*n-1,i);
	printf("%lld
",ans);
}