个人技术分享

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

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

用dxy[][0]存储每行的数，dxy[][1]存储每列的数

然后通过dfs搜索剪枝一下

• 加上当前枚举的数后超过l的
• 最后一行最后一列的

---

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 / n;
			int y = dep % n;

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

			// 最后一行一列时
			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;
		}
	}

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

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

	static StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	static PrintWriter out = new PrintWriter(System.out);

	static int ini() throws IOException
	{
		sc.nextToken();
		return (int) sc.nval;
	}

}

---

---

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

一起进步！！！

---

闪现