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