写了一个最简单的深搜 好像可以60 但是挂到10了
查看原帖
写了一个最简单的深搜 好像可以60 但是挂到10了
250699
mot1ve楼主2020/12/4 20:12
//搜索与回溯。
//八维暴搜 
#include<bits/stdc++.h>
#define int long long
using namespace std;
int ans,n,k;
int vis[20][20];
//以行为阶段开搜 
void dfs(int x,int y,int tot)//tot表示放了几个国王了。 
{
	if(x>n)//结束搜索 
	return ;
	if(y>n)//换行 
	{
		dfs(x+1,1,tot);
		return ;
	}
	if(tot==k)//满足要求 
	{
		ans++;
		return ;
	}
	if(vis[x][y]==0)//可以放 
	{
	vis[x][y]=1;//九维标记
	vis[x][y+1]=1;
	vis[x][y-1]=1;
	vis[x+1][y]=1;
	vis[x+1][y+1]=1;
	vis[x+1][y-1]=1;
	vis[x-1][y+1]=1;
	vis[x-1][y-1]=1;
	vis[x-1][y]=1;
	dfs(x,y+1,tot+1);//放 
	vis[x][y]=0;//九维标记
	vis[x][y+1]=0;
	vis[x][y-1]=0;
	vis[x+1][y]=0;
	vis[x+1][y+1]=0;
	vis[x+1][y-1]=0;
	vis[x-1][y+1]=0;
	vis[x-1][y-1]=0;
	vis[x-1][y]=0;
	}
	dfs(x,y+1,tot);//不放 
}
signed main()
{
	cin>>n>>k;
	dfs(1,1,0);
	cout<<ans;//方案数 
	return 0;
} 
2020/12/4 20:12
加载中...