杂题——吉利数组

L2-4：吉利矩阵

所有元素为非负整数，且各行各列的元素和都等于 7 的 3×3 方阵称为“吉利矩阵”，因为这样的矩阵一共有 666 种。
本题就请你统计一下，把 7 换成任何一个 [2,9] 区间内的正整数 L，把矩阵阶数换成任何一个 [2,4] 区间内的正整数 N，满足条件“所有元素为非负整数，且各行各列的元素和都等于 L”的 N×N 方阵一共有多少种？

输入格式：

输入在一行中给出 2 个正整数 L 和 N，意义如题面所述。数字间以空格分隔。

输出格式：

在一行中输出满足题目要求条件的方阵的个数。

输入样例：

1
7 3

输出样例：

1
666

原题

思路

​ 思路：这里我们就是最基本的DFS的思路，但是这里我们直接死遍历可能会超时，所以我们这里需要进行剪枝操作。具体请看下面代码。

代码（over）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
using namespace std;
int l,n,row[10],col[10],ans;
 
void bfs(int x){
    if(x == n * n){
        for(int i=0;i<n;i++){
            if(row[i]!=l) return;
            if(col[i]!=l) return;
        }
        ans++;
        return;
    }
    for(int i=0;i<=l;i++){//能填的数最小是0，最大是l
        //剪枝1：当前行或列值超过l
        if(row[x / n] + i > l || col[x % n] + i > l) break;
        row[x / n] += i;//对应行和更新
        col[x % n] += i;//对应列和更新
        //剪枝2：加上其他没有填的数（取最大）能达到l
        if(row[x / n] + l * (n - 1 - x % n) >= l && col[x % n] + l * (n - 1 - x / n)>=l)
            bfs(x + 1);
        row[x / n]-=i;//还原现场
        col[x % n]-=i;
    }
}
int main(){
    cin >> l >> n;
    bfs(0);
    cout << ans;
    return 0;
}