题目解析
所有元素为非负整数，且各行各列的元素和都等于L的N*N的方阵一共有多少种？
解题思路
和数独类似，只不过会比数独方便一点，只需要统计各行各列的元素和。
用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;
}
}