方格填数

ゝ一世哀愁。 2022-09-30 03:46 213阅读 0赞

方格填数

如下的10个格子  
\+–+–+–+  
| | | |  
\+–+–+–+–+  
| | | | |  
\+–+–+–+–+  
| | | |  
\+–+–+–+

（如果显示有问题，也可以参看【图1.jpg】）

填入0~9的数字。要求：连续的两个数字不能相邻。  
（左右、上下、对角都算相邻）

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

请填写表示方案数目的整数。  
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。  
分析: 暴力法 从a到j写 只考虑已有的数是否满足条件 避免重复  
a b c  
d e f g  
h i j  
![这里写图片描述][SouthEast]

#include <iostream>
    #include <cmath>
    using namespace std;
    int main()
    {   
        int count = 0;
        for(int a = 0; a < 10; a++)
            for(int b = 0; b < 10; b++) {
                if(abs(a-b)==1) continue;
                for(int c = 0; c < 10; c++) {
                    if(abs(c-b)==1) continue;
                    for(int d = 0; d < 10; d++) {
                        if(abs(d-a)==1) continue;
                        for(int e = 0; e < 10; e++) {
                            if(abs(e-d)==1 || abs(e-a)==1 || abs(e-b)==1) continue;
                            for(int f = 0; f < 10; f++) {
                                if(abs(f-e)==1 || abs(f-a)==1 || abs(f-b)==1 || abs(f-c)==1) continue;
                                for(int g = 0; g < 10; g++) {
                                    if(abs(g-f)==1 || abs(g-b)==1 || abs(g-c)==1)   continue;   
                                    for(int h = 0; h < 10; h++) {
                                        if(abs(h-d)==1 || abs(h-e)==1) continue;
                                        for(int i = 0; i < 10; i++) {
                                            if(abs(i-h)==1 || abs(i-d)==1 || abs(i-e)==1 || abs(i-f)==1) continue;
                                            for(int j = 0; j < 10; j++) {
                                                if(abs(j-i)==1 || abs(j-e)==1 || abs(j-f)==1 || abs(j-g)==1)    continue;
                                                count++;
                                            }
                                        }
                                    }
                                }
                            } 
                        } 
                    }
                }
            }
        cout << count;  
        return 0;
    }

全排列

#include <bits/stdc++.h>
    using namespace std;
    int main()
    {   
        int cnt = 0;
        int a[10] = {
       0,1,2,3,4,5,6,7,8,9};
        do{
            if(abs(a[1]-a[0])!=1 && abs(a[2]-a[1])!=1 && abs(a[4]-a[3])!=1
            && abs(a[3]-a[0])!=1 && abs(a[4]-a[0])!=1 && abs(a[4]-a[1])!=1 
            && abs(a[5]-a[4])!=1 && abs(a[5]-a[1])!=1 && abs(a[5]-a[0])!=1
            && abs(a[6]-a[5])!=1 && abs(a[6]-a[2])!=1 && abs(a[6]-a[1])!=1
            && abs(a[7]-a[3])!=1 && abs(a[7]-a[4])!=1 && abs(a[8]-a[7])!=1
            && abs(a[8]-a[3])!=1 && abs(a[8]-a[4])!=1 && abs(a[8]-a[5])!=1
            && abs(a[9]-a[8])!=1 && abs(a[9]-a[4])!=1 && abs(a[9]-a[6])!=1
            && abs(a[9]-a[5])!=1 && abs(a[5]-a[2])!=1) {
                cnt++;
            }
        }while(next_permutation(a, a+10));
        cout << cnt;
        return 0; 
    }

[SouthEast]: /images/20220708/5c820a59c5974eaa968c64d87fe1cc6b.png