L2-052 吉利矩阵

---

代码长度限制
16 KB
时间限制
1000 ms
内存限制
64 MB
栈限制
8192 KB

---

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

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

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

输入样例：
7 3
输出样例：
666

---

所有元素为非负整数，且各行各列的元素和都等于L的N*N的方阵一共有多少种？

---

emmmmmmm

和数独类似，只不过会比数独方便一点，只需要统计各行各列的元素和。

java过不去，时间究极TLE

---

import java.io.*;
import java.util.*;

public class Main
{
	static int N = 10 + 10;
	static int dxy[][] = new int[N][2]; // dxy[][0]统计的是x, dxy[][1]统计的是y
	static int l, n;
	static int ans = 0; // 统计方案数

	static void dfs(int dep)
	{
		if (dep >= n * n) // 如果这个方案成立
		{
			ans++;
			return;
		}

		for (int i = 0; i <= l; i++)
		{
			// 根据dep来计算(x, y)的坐标
			int x = dep / 3;
			int y = dep % 3;

            // 如果行或列的和超过l
			if (dxy[x][0] + i > l || dxy[y][1] + i > l) continue;

            // 最后一行一列时
			if (x == n - 1) i = n - dxy[y][1];
			if (y == n - 1) i = n - dxy[x][0];

            // 增加
			dxy[x][0] += i;
			dxy[y][1] += i;
			
			dfs(dep + 1); // 继续往下走
			
			// 回溯
			dxy[x][0] -= i;
			dxy[y][1] -= i;
		}
	}

	public static void main(String[] args)
	{
		l = sc.nextInt();
		n = sc.nextInt();
		dfs(0);
		out.println(ans);

		out.flush();
		out.close();
	}

	static Scanner sc = new Scanner(System.in);
	static PrintWriter out = new PrintWriter(System.out);

}

---

#include <iostream>

using namespace std;

const int N = 10 + 10;
int l, n;
int ans = 0;
int dxy[N][2];

void dfs(int dep)
{
    if(dep >= n * n)
    {
        ans ++;
        return;
    }
    
    for(int i = 0; i <= l; i ++)
    {
        int x = dep / n;
        int y = dep % n;
        
        if(dxy[x][0] + i > l || dxy[y][1] + i > l) break;
        
        if(x == n - 1) i = l - dxy[y][1];
        if(y == n - 1) i = l - dxy[x][0];
        
        dxy[x][0] += i;
        dxy[y][1] += i;
        dfs(dep + 1);
        dxy[x][0] -= i;
        dxy[y][1] -= i;
    }
}

int main()
{
    cin >> l >> n;
    dfs(0);
    cout << ans;
    
    return 0;
}

---

---

如果有说错的 或者 不懂的 尽管提 嘻嘻

一起进步！！！

---

闪现