L2-052 吉利矩阵 - 团体程序设计天梯赛-练习集
所有元素为非负整数，且各行各列的元素和都等于 7 的 3×3 方阵称为“吉利矩阵”，因为这样的矩阵一共有 666 种。
本题就请你统计一下，把 7 换成任何一个 [2,9] 区间内的正整数 L，把矩阵阶数换成任何一个 [2,4] 区间内的正整数 N，满足条件“所有元素为非负整数，且各行各列的元素和都等于 L”的 N×N 方阵一共有多少种？
输入格式：
输入在一行中给出 2 个正整数 L 和 N，意义如题面所述。数字间以空格分隔。
输出格式：
在一行中输出满足题目要求条件的方阵的个数。
输入样例：
7 3
输出样例：
666
思路：
剪枝只对完成的行列进行判断，超时两个点
代码：
#include <bits/stdc++.h>
using namespace std;
int a[10][10];
int rows[10], ranks[10];
int L, N, ans;void dfs(int x, int y)
{if (y > N)// 走完一行 { if (rows[x] != L)return;x++;y = 1;}if (x > N) // 填充完整个矩阵 {for (int i = 1; i <= N; i++) {if (ranks[i] != L)return;if(rows[i] != L)return;}ans++;return;}for (int i = 0; i <= L; i++) {a[x][y] = i;rows[x] += i;ranks[y] += i;dfs(x, y + 1);rows[x] -= i;ranks[y] -= i;a[x][y] = 0;}
}int main(void)
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> L >> N;dfs(1, 1);cout << ans;return 0;
}
思路：
优化剪枝，对于中间过程，凡是超过L的都要回溯，这里利用两个数组，存行和列的值。超时一个点。
代码：
#include <bits/stdc++.h>
using namespace std;
int a[10][10];
int rows[10], ranks[10];
int L, N, ans;void dfs(int x, int y)
{if(rows[x] > L || ranks[y] > L)return; if (y > N)//走完一行 { if (rows[x] != L)return;x++;y = 1;}if (x > N)// 填充完整个矩阵 { for (int i = 1; i <= N; i++) {if (ranks[i] != L)return;}ans++;return;}for (int i = 0; i <= L; i++) {a[x][y] = i;rows[x] += i;ranks[y] += i;dfs(x, y + 1);rows[x] -= i;ranks[y] -= i;a[x][y] = 0;}
}int main(void) {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> L >> N;dfs(1, 1);cout << ans;return 0;
}
思路：
完全优化，对于行最后一个位置，不用进行枚举，直接求L-（N-1）选的数字和。
代码：
#include <bits/stdc++.h>
using namespace std;int rows[10], ranks[10];
int L, N, ans;void dfs(int x, int y)
{if (x > N)//全部走完 {ans++;return;}if (y > N) //走完一行 {if (rows[x] != L) return;x++;y = 1; }if (rows[x] > L || ranks[y] > L)//剪枝 return;if (y == N)//每行最后一个格子 {int remain = L - rows[x];if (remain < 0 || ranks[y] + remain > L) return;rows[x] += remain;ranks[y] += remain;dfs(x, y + 1);rows[x] -= remain;ranks[y] -= remain;} else {int max_i = min(L - rows[x], L - ranks[y]);//取最小 for (int i = 0; i <= max_i; i++) {rows[x] += i;ranks[y] += i;dfs(x, y + 1);rows[x] -= i;ranks[y] -= i;}}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> L >> N;dfs(1, 1);cout << ans;return 0;
}
