首页 » C++ » 方格填数

方格填数

原文 http://blog.csdn.net/Soul_97/article/details/79168764

2018-01-27 02:00:50阅读(503)

如下的10个格子

   +--+--+--+

   | |  |  |

+--+--+--+--+

|  | |  |  |

+--+--+--+--+

|  | |  |

+--+--+--+

入0~9的数字。要求:连续的两个数字不能相邻。

(左右、上下、对角都算相邻)

一共有多少种可能的填数方案?


思路:如果用一维数组来处理的话,把格子标号,然后写规则,每个数字的相邻的规则多达四五条,加起来一共几十条,手写较容易出错

这时可以想到邻接矩阵的思想,那就是创建一个二维数组,然后对应的格子制定规则,如果相邻标为1,不相邻标为0,  这样去简化写规则。

在枚举的时候可以直接枚举格子里的数字是否满足而不是枚举格子是否符合相邻关系


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[10];
int adj[10][10] = {{0, 1, 0, 1, 1, 1, 0, 0, 0, 0},
                {1, 0, 1, 0, 1, 1, 1, 0, 0, 0},
                {0, 1, 0, 0, 0, 1, 1, 0, 0, 0},
                {1, 0, 0, 0, 1, 0, 0, 1, 1, 0},
                {1, 1, 0, 1, 0, 1, 0, 1, 1, 1},
                {1, 1, 1, 0, 1, 0, 1, 0, 1, 1},
                {0, 1, 1, 0, 0, 1, 0, 0, 0, 1},
                {0, 0, 0, 1, 1, 0, 0, 0, 1, 0},
                {0, 0, 0, 1, 1, 1, 0, 1, 0, 1},
            	{0, 0, 0, 0, 1, 1, 1, 0, 1, 0}};
bool ok()
{
	for(int i = 0;i < 9;i ++)
	{
		if(adj[a[i]][a[i+1]]) return false;
	}
	return true;
} 
int main()
{
	for(int i = 0;i <= 9;i ++)
	a[i]= i;
	
	ll ans = 0;
	do{
		if(ok())
		ans ++;
	}while(next_permutation(a,a+10));
	cout<<ans<<endl;
	return 0; 
} 

还可以从逻辑关系上判断,给格子编行和列,然后根据关系写出对应的式子

int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
bool adj(int x, int y) {
        int rx = x / 4, cx = x % 4, ry = y / 4, cy = y % 4;
        return abs(rx - ry) <= 1 && abs(cx - cy) <= 1;
}
bool ok() {
        for(int i = 0; i < 9; i++)
                if(adj(a[i], a[i+1])) return false;
        return true;
} 
int main(){
        int ans = 0;
        for(int i = 0; i < 10*9*8*7*6*5*4*3*2*1; i++) {
                if(ok()) ans++;
                next_permutation(a, a+10);
        }
        cout << ans << endl;
        return 0;
}




最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹