L2-052 吉利矩阵分

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;
}