吉利矩阵（DFS）

所有元素为非负整数，且各行各列的元素和都便是 7 的 3×3 方阵称为 “吉利矩阵”，因为这样的矩阵一共有 666 种。
本题就请你统计一下，各行各列的元素和都便是 5 的 3×3 方阵一共有多少种？
思路：统计方法数，且数据不大，以是可以考虑DFS
细节：if(x==n-1&&sy[y]+i<s) continue;表示如果这是末了一行，那么如果每一列加上i还是不能到达s的话，那就说明不可取，大概也可以写成  if(x==n-1&&s[y]<l) i=s-s[y];这样就省去了一个个遍历了。
其中x表示某一行，y表示某列

1. #include<iostream>
2. using namespace std;
3. #define int long long
4. const int N=9;
5. int ans=0;
6. int s,n;
7. int sx[N];
8. int sy[N];
9. void dfs(int j)
10. {
11.         if(n*n==j)
12.         {
13.                 ans+=1;
14.                 return;
15.         }
16.         for(int i=0;i<=s;i++)
17.         {
18.                 int x,y;
19.                 x=j/n;
20.                 y=j%n;
21.                 if(sx[x]+i>s||sy[y]+i>s) continue;
22.                 if(x==n-1&&sy[y]+i<s) continue;
23.                 sx[x]+=i;
24.                 sy[y]+=i;
25.                 dfs(j+1);
26.                 sx[x]-=i;
27.                 sy[y]-=i;
28.         }
29. }
30. signed main()
31. {
32.         ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
33.         cin>>s>>n;
34.         dfs(0);
35.         cout<<ans<<endl;
36.         return 0;
37. }

复制代码

 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。