提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

蓝桥杯题目——飞行员兄弟解题详解及其包含的思想

详解 及其 包含 蓝桥 题目 解题 思想 兄弟
2023-06-13 09:16:56 时间

前言

本文介绍蓝桥杯题目——飞行员兄弟的解题方法及其包含的代码思想。

题目信息

“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 16 个把手的冰箱。

已知每个把手可以处于以下两种状态之一：打开或关闭。

只有当所有把手都打开时，冰箱才会打开。

把手可以表示为一个 4×4的矩阵，您可以改变任何一个位置 i,j上把手的状态。

但是，这也会使得第 i行和第j列上的所有把手的状态也随着改变。

请你求出打开冰箱所需的切换把手的次数的最小值是多少。

输入格式

输入一共包含四行，每行包含四个把手的初始状态。

符号 + 表示把手处于闭合状态，而符号 - 表示把手处于打开状态。

至少一个手柄的初始状态是关闭的。

输出格式

第一行输出一个整数 N，表示所需的最小切换把手次数。

接下来 N行描述切换顺序，每行输出两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。

注意： 如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。

输入样例

-+--
----
----
-+--

输出样例

6
1 1
1 3
1 4
4 1
4 3
4 4

数据范围

1<=i，j<=4

解题方法

本题推荐使用暴力方法解答，原因如下：

  1. 每个把手只有2种情况——打开或关闭，因此对同一个位置的多次操作是没有意义的。
  2. 每个把手处于打开还是关闭状态只取决于初始状态和对其操作的次数，因此对不同位置操作的顺序是任意的。
  3. 只有4x4=16个把手，数据足够小，满足使用暴力方法解决的条件。

代码实现

主函数

首先，创造一个4x4的数组sou读入题目给出的数据，利用1代表把手处于关闭状态，利用-1代表把手处于打开状态。

int sou[4][4];
int main()
{
	int n = 0;
	for (int i = 0; i < 4; i++)
	{
		for (int j = 0; j < 4; j++)
		{
			scanf("%1c", &n);
			if (n == '+')
			{
				sou[i][j] = 1;
			}
			else if (n == '-')
			{
				sou[i][j] = -1;
			}
		}
		getchar();
	}
	dfs(0);
}

递归函数

其次，完成对16个位置的枚举，创建数组arr记录每个位置是否选择，将每一种枚举情况传入判断函数。

int sou[4][4];
int arr[16];
void dfs(int step)
{
	if (step == 16)
	{
		if (kennka())
		{
			print();
			return;
		}
		else
		{
			return;
		}
	}
	//xuan
	arr[step] = 1;
	dfs(step + 1);
	arr[step] = 0;

	//buxuan
	dfs(step + 1);
}

判断函数

再其次，对每一种传入的枚举情况进行判断。

先创建一个临时的数组_ sou并从sou拷贝信息，用来保存每一次操作后把手的情况，以避免与其他情况下混淆。

随后创建一个变量min_ count并使其初始化为一个大于16的值，用来保存并更新每一种成功的情况用了多少步。

因为题目要求输出每一次操作时的下标，所以在判断之前要先统计一下该种情况的操作步数是否小于min_count，如果小于，代表这种情况有可能成为答案；如果大于，代表这种情况即使满足所有把手都打开，也不是最优解，不能成为答案。

在进行判断之前，创建结构体fxy保存每一次操作的下标，同时利用变量count记录操作了几次。一旦某种情况可行，就把min_count更新为count，同时返回1；否则返回0。

int sou[4][4];
int arr[16];
int min_count = 20;
struct fxy
{
	int _a;
	int _b;
};
struct fxy mem[100] = { 0 };
int kennka()
{
	int _sou[4][4];
	memcpy(_sou, sou, 16 * 4);
	int count = 0;
	for (int i = 0; i < 16; i++)
	{
		if (arr[i] == 1)
		{
			count++;
		}
	}
	if (count >= min_count)
	{
		return 0;
	}
	count = 0;
	for (int i = 0; i < 16; i++)
	{
		if (arr[i] == 1)//相当于按了_sou【i/4】【i%4】
		{
			int a = i / 4;
			int b = i % 4;
			mem[count]._a = a+1;
			mem[count]._b = b+1;
			count++;
			_sou[a][b] *= -1;
			for (int j = 0; j < 4; j++)
			{
				_sou[a][j] *= -1;
			}
			for (int i = 0; i < 4; i++)
			{
				_sou[i][b] *= -1;
			}
		}
	}
	for (int i = 0; i < 4; i++)
	{
		for (int j = 0; j < 4; j++)
		{
			if (_sou[i][j]==1)
			{
				return 0;
			}
		}
	}
	min_count = count;
	return 1;

}

输出函数

由于min_count的初始值是20，所以只要有一个成立的情况，min_count就一定会被改变。

又因为一旦有一种成立的情况的操作步数小于min_count，min_count就会被更新，所以此时的min_count一定是最优解。

利用该变量打印出每次操作位置的下标即可。

void print()
{
	printf("%d\n", min_count);
	for (int i = 0; i < min_count; i++)
	{
		printf("%d %d\n", mem[i]._a, mem[i]._b);
	}
	return;
}

思想总结

思想（1）

在我们读入数据时，博主并没有直接在数组中保存+或-,而是利用1和-1分别代表两种符号，这样做的好处是在改变状态时可以直接让其乘以-1，而不用再去判断是加号还是减号，可以简化代码。

思想（2）

在我们枚举每一种情况时，博主并没有创建一个4x4的arr来存储每一种位置是否被选择，而是利用了一个一维数组，将其下标除以4作为行，模以4作为列，以此来表示_ sou中的每一个数，这样做的好处是可以简化代码。

思想（3）

在进行循环操作时，博主总是在for语句的那一行创建循环变量，这样做的好处是可以避免上一次循环后忘记初始化的问题。

感谢您的阅读与耐心~

相关文章