非递归实现组合型枚举、费解的开关（贪心）

非递归实现组合型枚举

题目描述

运行代码

#include <iostream>
#include <vector>
using namespace std;
void FN(int n, int m, vector<int>& s, int start) {
    if (s.size() == m) {
        for (int num : s) {
            cout << num << " ";
        }
        cout<<endl;
        return;
    }

    for (int i = start; i <= n; i++) {
        s.push_back(i);
        FN(n, m,s, i + 1);
        s.pop_back();
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> ss;
   FN(n, m, ss, 1);

    return 0;
}

代码思路

FN函数使用回溯法来生成从1到n中选m个数的所有组合。
当组合的长度达到m时，就输出该组合。
通过一个循环从当前起始位置开始尝试添加每个数到组合中，然后递归调用自身继续生成，最后弹出刚才添加的数进行回溯。

改进思路

添加一些边界条件判断来增强代码的健壮性

改进代码

#include <iostream>
#include <vector>
using namespace std;

void FN(int n, int m, vector<int>& s, int start) {
    if (s.size() == m) {
        for (int num : s) {
            cout << num << " ";
        }
        cout << endl;
        return;
    }

    if (start > n) { // 添加边界条件判断
        return;
    }

    for (int i = start; i <= n; i++) {
        s.push_back(i);
        FN(n, m, s, i + 1);
        s.pop_back();
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> ss;
    FN(n, m, ss, 1);

    return 0;
}

费解的开关

题目描述

运行代码

#include <cstring>
#include <iostream>
using namespace std;
const int N = 6;
int a[N], ans, aa[N];
char s[N];

void dj(int x, int y) {
	aa[x] ^= (1 << y);
	if (x != 1) aa[x-1] ^= (1 << y);
	if (x != 5) aa[x+1] ^= (1 << y);
	if (y != 0) aa[x] ^= (1 << (y - 1));
	if (y != 4) aa[x] ^= (1 << (y + 1));
}

void pd(int p) {
	int k = 0;
	memcpy(aa, a, sizeof(a));
	for (int i = 0; i < 5; i++)
		if (!((p >> i) & 1)) {
			dj(1, i);
			if (++k >= ans) return;
		}
	for (int x = 1; x < 5; x++)
		for (int y = 0; y < 5; y++)
			if (!((aa[x] >> y) & 1)) {
				dj(x + 1, y);
				if (++k >= ans) return;
			}
	if (aa[5] == 31) ans = k;
}

void abc() {
	memset(a, 0, sizeof(a));
	for (int i = 1; i <= 5; i++) {
		cin >> (s + 1);
		for (int j = 1; j <= 5; j++) a[i] = (a[i] << 1)+ (s[j] - '0');
	}
	ans = 7;
	for (int p = 0; p < (1 << 5); p++) pd(p);
	if (ans == 7) cout << "-1" << endl;
	else cout << ans << endl;
}

int main() {
	int n;
	cin >> n;
	while (n--) abc();
	return 0;
}

代码思路

变量定义:
- N = 6 表示处理的数组大小，但实际上代码逻辑暗示着处理的是一个5x5的矩阵，因为有for (int i = 0; i < 5; i++)这样的循环。
- a[N] 和 aa[N] 是两个整型数组，用于存储当前状态和操作后的状态，每个元素用一个整数的低5位表示矩阵的一行，其中1表示灯亮，0表示灯灭。
- ans 存储最小的操作步数。
- s[N] 用于读取输入的字符串。
函数dj (toggle):对矩阵的一个位置(x, y)执行开关操作，并同时影响其上、下、左、右的邻居。这里使用位异或操作(1 << y)来翻转指定位置的灯的状态，以及其相邻的位置。
函数pd (processDirection):接受一个方向选择参数p，该参数决定哪些初始位置的灯应该被操作。通过遍历所有可能的方向组合，调用dj函数进行状态转换，并记录操作步数k。如果某次操作使得最后一行(索引为5)的所有灯都亮起(aa[5] == 31)，则更新ans为当前的步数k。
函数abc (solveProblem):
- 读取输入，将字符矩阵转化为二进制表示的整数数组a。
- 初始化ans为最大可能步数7，然后对所有可能的初始操作组合调用pd函数。
- 最后，输出最小操作步数或-1表示无解。
main函数:读取测试用例数量n，然后循环调用abc函数处理每个案例。