L2-052 吉利矩阵

2024-04-22 16:28

文章标签 矩阵吉利 l2 052

本文主要是介绍L2-052 吉利矩阵，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

在这里插入图片描述

题解思路

这个道题就是很简单，就跟n皇后问题一样，给矩阵填数，使得矩阵满足一个什么条件，最后求方案数或者方案。很容易想到回溯法，根据数据范围，应该能够确定回溯法是没有问题的。
我们只需要枚举矩阵的每一个位置，给这个位置填上一个数，如果满足条件，我们就枚举下一个位置。这里的满足条件是指，如果当前位置是某一行的最后一个位置或者某一列的最后一个位置，那么我们需要保证填上这个数之后当前行或列的数字之后等于L。
为了实现简单，我们使用xx[]来表示行的和，yy[]来表示列的和。枚举位置的时候我们使用像解八数码问题那样，使用一个数idx来枚举，idx/n就是横坐标，idx%n就是纵坐标，再加上一点剪枝就没有问题。

代码实现

Java

Java超时了，真够离谱的

import java.util.Scanner;public class Main {static int l, n, ans;static int[] xx = new int[5], yy = new int[5];public static void main(String[] args) {Scanner in = new Scanner(System.in);l = in.nextInt();n = in.nextInt();dfs(0);System.out.println(ans);}public static void dfs(int idx) {if (n * n == idx) {ans ++;return;}for (int i = 0; i <= l; i ++) {int x, y;x = idx / n;y = idx % n;if (xx[x] + i > l || yy[y] + i > l) continue;/*** if (x == n - 1 && yy[y] + i < l) continue;* if (y == n - 1 && xx[x] + i < l) continue;* 本来以为是这里浪费时间了，* 就改成下边那个，代码速度一定提高了，* 但java还是超时， C/C++两个都可以过，下边的更快*/if (x == n - 1 ) i = l - yy[y];if (y == n - 1 ) i = l - xx[x];xx[x] += i;yy[y] += i;dfs(idx + 1);xx[x] -= i;yy[y] -= i;}}
}

C/C++

#include <iostream>
using namespace std;
int l, n, ans;
int xx[5], yy[5];
void dfs(int);
int main() {cin >> l >> n;dfs(0);cout << ans;return 0;
}
void dfs(int idx) {if (n * n == idx) {ans ++;return;}for (int i = 0; i <= l; i ++) {int x, y;x = idx / n;y = idx % n;if (xx[x] + i > l || yy[y] + i > l) continue;if (x == n - 1 ) i = l - yy[y];// if (x == n - 1 && yy[y] + i < l) continue;本来是这个，但是我们可以直接让i等于我们需要的那个值。两种都可以过if (y == n - 1 ) i = l - xx[x];xx[x] += i;yy[y] += i;dfs(idx + 1);xx[x] -= i;yy[y] -= i;}
}