70pts超时求助
查看原帖
70pts超时求助
741424
ertree楼主2022/10/22 17:04
#include <iostream>
//#pragma GCC optimize(2)
//using namespace std;
const int N=15;
char a[N][N],b[N],c[2*N],e[2*N],g[N];
int n,ans;
inline void dfs(int step)
{
	if(step==n+1)
	{
		++ans;
		return ;
	}
	if(!b[1]&&!c[1+step]&&!e[n+1-step]&&a[step][1-1]=='*')
	{
		b[1]=c[1+step]=e[n+1-step]=1;
		dfs(step+1);
		b[1]=c[1+step]=e[n+1-step]=0;
	}
	if(n>=2)
	{
		if(!b[2]&&!c[2+step]&&!e[n+2-step]&&a[step][2-1]=='*')
		{
			b[2]=c[2+step]=e[n+2-step]=1;
			dfs(step+1);
			b[2]=c[2+step]=e[n+2-step]=0;
		}
		if(n>=3)
		{
			if(!b[3]&&!c[3+step]&&!e[n+3-step]&&a[step][3-1]=='*')
			{
				b[3]=c[3+step]=e[n+3-step]=1;
				dfs(step+1);
				b[3]=c[3+step]=e[n+3-step]=0;
			}
			if(n>=4)
			{
				if(!b[4]&&!c[4+step]&&!e[n+4-step]&&a[step][4-1]=='*')
				{
					b[4]=c[4+step]=e[n+4-step]=1;
					dfs(step+1);
					b[4]=c[4+step]=e[n+4-step]=0;
				}
				if(n>=5)
				{
					if(!b[5]&&!c[5+step]&&!e[n+5-step]&&a[step][5-1]=='*')
					{
						b[5]=c[5+step]=e[n+5-step]=1;
						dfs(step+1);
						b[5]=c[5+step]=e[n+5-step]=0;
					}
					if(n>=6)
					{
						if(!b[6]&&!c[6+step]&&!e[n+6-step]&&a[step][6-1]=='*')
						{
							b[6]=c[6+step]=e[n+6-step]=1;
							dfs(step+1);
							b[6]=c[6+step]=e[n+6-step]=0;
						}
						if(n>=7)
						{
							if(!b[7]&&!c[7+step]&&!e[n+7-step]&&a[step][7-1]=='*')
							{
								b[7]=c[7+step]=e[n+7-step]=1;
								dfs(step+1);
								b[7]=c[7+step]=e[n+7-step]=0;
							}
							if(n>=8)
							{
								if(!b[8]&&!c[8+step]&&!e[n+8-step]&&a[step][8-1]=='*')
								{
									b[8]=c[8+step]=e[n+8-step]=1;
									dfs(step+1);
									b[8]=c[8+step]=e[n+8-step]=0;
								}
								if(n>=9)
								{
									if(!b[9]&&!c[9+step]&&!e[n+9-step]&&a[step][9-1]=='*')
									{
										b[9]=c[9+step]=e[n+9-step]=1;
										dfs(step+1);
										b[9]=c[9+step]=e[n+9-step]=0;
									}
									if(n>=10)
									{
										if(!b[10]&&!c[10+step]&&!e[n+10-step]&&a[step][10-1]=='*')
										{
											b[10]=c[10+step]=e[n+10-step]=1;
											dfs(step+1);
											b[10]=c[10+step]=e[n+10-step]=0;
										}
										if(n>=11)
										{
											if(!b[11]&&!c[11+step]&&!e[n+11-step]&&a[step][11-1]=='*')
											{
												b[11]=c[11+step]=e[n+11-step]=1;
												dfs(step+1);
												b[11]=c[11+step]=e[n+11-step]=0;
											}
											if(n>=12)
											{
												if(!b[12]&&!c[12+step]&&!e[n+12-step]&&a[step][12-1]=='*')
												{
													b[12]=c[12+step]=e[n+12-step]=1;
													dfs(step+1);
													b[12]=c[12+step]=e[n+12-step]=0;
												}
												if(n>=13)
												{
													if(!b[13]&&!c[13+step]&&!e[n+13-step]&&a[step][13-1]=='*')
													{
														b[13]=c[13+step]=e[n+13-step]=1;
														dfs(step+1);
														b[13]=c[13+step]=e[n+13-step]=0;
													}
													if(n>=14)
													{
														if(!b[14]&&!c[14+step]&&!e[n+14-step]&&a[step][14-1]=='*')
														{
															b[14]=c[14+step]=e[n+14-step]=1;
															dfs(step+1);
															b[14]=c[14+step]=e[n+14-step]=0;
														}
													}
												}
											}
										}
									}
								}
							}
						}
					}
				}
			}
		}
	}
//	for(int i=1;i<=n;++i)
//	{
//		if(!b[i]&&!c[i+step]&&!e[n+i-step]&&a[step][i-1]=='*')
//		{
//			b[i]=c[i+step]=e[n+i-step]=1;
//			dfs(step+1);
//			b[i]=c[i+step]=e[n+i-step]=0;
//		}
//	}
	return ;
}
int main()
{
	scanf("%d",&n);
	int j;
	for(int i=1; i<=n; ++i)
	{
		scanf("%s",a[i]);
	}
	dfs(1);
	printf("%d",ans);
	return 0;
}

只有O2才能过

2022/10/22 17:04
加载中...