洛谷P1092虫食算——深搜

题目：https://www.luogu.org/problemnew/show/P1092

剪枝1：从右往左、从上往下按字母出现顺序搜索；

剪枝2：同一列前两个数字确定，可直接算出第三个数字并判断；

剪枝3：每次搜索前看看前面的列上有没有已经不符合的情况(进位最多为1)；

代码如下：

#include<iostream>

#include<cstdio>

using namespace std;

int n,c[300],jin[30];

char a[5][30];

bool vis[30],p[300];

bool check(int y)

{

	for(int i=y;i>=0;i--)

		if(p[a[1][i]]&&p[a[2][i]]&&p[a[3][i]]&&

		((c[a[1][i]]+c[a[2][i]])%n!=c[a[3][i]])&&

		((c[a[1][i]]+c[a[2][i]]+1)%n!=c[a[3][i]]))return 1;

	return 0;

}

void ser(int x,int y)

{

	if(check(y))return;

	if(y<0)

	{

		for(int i=65;i<=91;i++)

			if(p[i])

				printf("%d ",c[i]);

		return;

	}

	if(x==3)

	{

		int k=c[a[1][y]]+c[a[2][y]]+jin[y];

		int t=0;

		while(k>=n)t++,k-=n;

		jin[y-1]=t;

//		printf("y=%d k=%d jin[%d]=%d\n",y,k,y,jin[y]);

//		jin[y]=0;

		if(!p[a[x][y]]&&!vis[k])

		{

//			printf("%c=%d\n",a[x][y],k);

			c[a[x][y]]=k;

			p[a[x][y]]=1;

			vis[k]=1;

			ser(1,y-1);

			c[a[x][y]]=0;

			p[a[x][y]]=0;

			vis[k]=0;

			return;

		}

		else if(p[a[x][y]]&&vis[k]&&c[a[x][y]]==k)

		{

			ser(1,y-1);

			return;

		}

		else

		{

//			jin[y-1]=0;

			return;

		}

	}

	else if(!p[a[x][y]])

	{

		for(int i=0;i<n;i++)

		{

			if(!vis[i])

			{

//				printf("x=%d y=%d a=%c i=%d\n",x,y,a[x][y],i);

				c[a[x][y]]=i;

				p[a[x][y]]=1;

				vis[i]=1;

				ser(x+1,y);

				c[a[x][y]]=0;

				p[a[x][y]]=0;

				vis[i]=0;

			}

		}

	}

	else ser(x+1,y);

}

int main()

{

	scanf("%d ",&n);

	cin>>a[1];

	cin>>a[2];

	cin>>a[3];

	ser(1,n-1);

	return 0;

}

/*

20 NLHFIEASBRQJOGKMDPCT

NQGPSIIGKDMFDCBFMQSO

PNKNTOLHEIJHFGJKHJGG

*/