2017蓝桥模拟赛滑动解锁（深搜条件判断）

痛定思痛。 2022-09-30 06:04 134阅读 0赞

参考了这位大牛http://blog.csdn.net/su20145104009/article/details/51317793

还有知乎里https://www.zhihu.com/question/24905007

389112种方案的计算方法，直接上代码，

#include<iostream>
    using namespace std;
    int no[10][10]={0},v[10]={0},cnt=0,a[10]={0};
    void dfs(int x)
    {
    	int i;
    	if (x>4)
    	{
    		cnt++;
    	}
    	for (i=1; i<=9; i++)
    	{
    		if (!v[i])
    		{
    			if (x>1)
    			{
    				if (no[i][a[x-1]]  //如果当前选的点(i)和上一个选的点(a[x-1])是跨点的，比如1和9跨5,1和3跨2 
    				&& !v[no[i][a[x-1]]]) //那么两个点中间的点是必须被走过的，假如没走过就是非法的 
    				continue;
    			}
    			a[x] = i;
    			v[i] = 1;
    			dfs(x+1);
    			v[i] = 0;
    		}
    	}
    }
    int main()
    {
    	no[1][3] = no[3][1] = 2; //1和3 3和1两个点之间是2,把这总中间隔着点的两个点列举出来
    	no[1][9] = no[9][1] = 5;
    	no[1][7] = no[7][1] = 4;
    	no[2][8] = no[8][2] = 5;
    	no[3][7] = no[7][3] = 5;
    	no[4][6] = no[6][4] = 5;
    	no[7][9] = no[9][7] = 8;
    	no[3][9] = no[9][3] = 6;
    	dfs(1);
    	cout<<cnt;
    	return 0;
    }

蓝桥题目代码：

#include<iostream>
    using namespace std;
    int no[10][10]={0},v[10]={0},cnt=0,a[10]={0};
    int n,f[9][2]={0};
    int check(int x)
    {
    	int i,j; 
    	for (i=1; i<=n; i++) 
    	{
    		for (j=2; j<=x; j++)
    		{
    			if ((a[j]==f[i][0] && a[j-1]==f[i][1]) || (a[j]==f[i][1]&&a[j-1]==f[i][0])) //两个点是相连的
    			 break;
    		}
    		if (j>x)
    		 return 0;
        }
    	return 1;
    }
    void dfs(int x)
    {
    	int i;
    	if (x>4)
    	{
    		if (check(x-1))
    		{
    			cnt++;
    		}
    		
    	}
    	for (i=1; i<=9; i++)
    	{
    		if (!v[i])
    		{
    			if (x>1)
    			{
    				if (no[i][a[x-1]]  //如果当前选的点(i)和上一个选的点(a[x-1])是跨点的，比如1和9跨5,1和3跨2 
    				&& !v[no[i][a[x-1]]]) //那么两个点中间的点是必须被走过的，假如没走过就是非法的 
    				continue;
    			}
    			a[x] = i;
    			v[i] = 1;
    			dfs(x+1);
    			v[i] = 0;
    		}
    	}
    }
    int main()
    {
    	int i,j;
    	no[1][3] = no[3][1] = 2;
    	no[1][9] = no[9][1] = 5;
    	no[1][7] = no[7][1] = 4;
    	no[2][8] = no[8][2] = 5;
    	no[3][7] = no[7][3] = 5;
    	no[4][6] = no[6][4] = 5;
    	no[7][9] = no[9][7] = 8;
    	no[3][9] = no[9][3] = 6;
    	cin>>n;
    	if (n == 0)
    	{
    		cout<<389112;
    		return 0;
    	}
    	for (i=1; i<=n; i++)
    	{
    		cin>>f[i][0]>>f[i][1];
    	}
    	dfs(1);
    	cout<<cnt;
    	return 0;
    }