为什么加了剪枝还是全T?
查看原帖
为什么加了剪枝还是全T?
250699
mot1ve楼主2021/3/11 15:20
//搜索+一堆剪枝
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[20][20],vis[20];
void print()
{
	for(int i=1;i<=4;i++)
	{
		for(int j=1;j<=4;j++)
		{
			cout<<a[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<endl; 
}
bool check()
{
	if(a[1][1]&&a[1][4]&&a[4][1]&&a[4][4]&&(a[1][1]+a[1][4]+a[4][1]+a[4][4]!=34))
	return 0;
	if(a[1][1]&&a[1][2]&&a[2][1]&&a[2][2]&&(a[1][1]+a[1][2]+a[2][1]+a[2][2]!=34))
	return 0;
	if(a[2][2]&&a[2][3]&&a[3][2]&&a[3][3]&&(a[2][2]+a[2][3]+a[3][2]+a[3][3]!=34))
	return 0;
	if(a[1][1]&&a[2][2]&&a[3][3]&&a[4][4]&&(a[1][1]+a[2][2]+a[3][3]+a[4][4]!=34))
	return 0;
	if(a[1][4]&&a[2][3]&&a[3][2]&&a[4][1]&&(a[1][4]+a[2][3]+a[3][2]+a[4][1]!=34))
	return 0;
	for(int i=1;i<=4;i++)
	{
		if(a[1][i]&&a[2][i]&&a[3][i]&&a[4][i]&&(a[1][i]+a[2][i]+a[3][i]+a[4][i]!=34))
		return 0;
	}
	return 1;
}
//x表示行,y表示列 
void dfs(int x,int y)
{
	if(!check())
	{
		return ;
	}
	if(x>4)//填完了,并且合法 
	{
		print();
		return ;
	}
	if(y>4)
	{
		if(a[x][1]+a[x][2]+a[x][3]+a[x][4]!=34)
		return ;
		else dfs(x+1,1);
	}
	for(int i=2;i<=16;i++)
	{
		if(!vis[i])
		{
			a[x][y]=i;
			vis[i]=1;
			dfs(x,y+1);
			vis[i]=0;
			a[x][y]=0;
		}
	}
}
int main()
{
	cin>>n>>m;
	a[n][m]=1;
	dfs(1,1);
	return 0;
} 
2021/3/11 15:20
加载中...