POJ – 2965 – The Pilots Brothers' refrigerator (高效贪心!!)[通俗易懂]

POJ – 2965 – The Pilots Brothers' refrigerator (高效贪心!!)

大家好,又见面了,我是全栈君。

The Pilots Brothers’ refrigerator
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 19356   Accepted: 7412   Special Judge

Description

The game “The Pilots Brothers: following the stripy elephant” has a quest where a player needs to open a refrigerator.

There are 16 handles on the refrigerator door. Every handle can be in one of two states: open or closed. The refrigerator is open only when all handles are open. The handles are represented as a matrix 4х4. You can change the state of a handle in any location [i, j] (1 ≤ i, j ≤ 4). However, this also changes states of all handles in row i and all handles in column j.

The task is to determine the minimum number of handle switching necessary to open the refrigerator.

Input

The input contains four lines. Each of the four lines contains four characters describing the initial state of appropriate handles. A symbol “+” means that the handle is in closed state, whereas the symbol “−” means “open”. At least one of the handles is initially closed.

Output

The first line of the input contains N – the minimum number of switching. The rest N lines describe switching sequence. Each of the lines contains a row number and a column number of the matrix separated by one or more spaces. If there are several solutions, you may give any one of them.

Sample Input

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

Sample Output

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

Source

Northeastern Europe 2004, Western Subregion

看着ACM练习建议去做的,,上面说的是枚举。。

可是我枚举了半天。。没搞出来


网上搜了下别人的题解,都是说有高效贪心算法。然后琢磨半天搞懂了


比方:

-+–

—-

—-

—-

要把这个改成全是减号就必须将+号所在行和所在列的符号所有都改变一次(+号所在位置改变一次就可以)

所以有例如以下改变次数:

4744

2422

2422

2422

当中7是+号位置所需改变的次数,4是+号所在行和所在列(不包含+号)所需改变次数

因此得出高效解法,在每次输入碰到’+’的时候, 计算所在行和列的须要改变的次数

当输入结束后,遍历数组,全部为奇数的位置则是操作的位置,而奇数位置的个数之和则是终于的操作次数.

但这样的算法仅仅对n为偶数时适用

PS:该题不会有”Impossible”的情况.


AC代码:


#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int a[5][5];

int main()
{
	char c;
	memset(a, 0, sizeof(a));
	for(int i=1; i<=4; i++)
		for(int j=1; j<=4; j++)
		{
			c = getchar();
			while(c == '\n') c = getchar();
			if(c == '+')
			{
				for(int k=1; k<=4; k++)
				{
					a[i][k]++;
					a[k][j]++;
				}
				a[i][j]--;
			}
		}
	int sum = 0;
	for(int i=1; i<=4; i++)
		for(int j=1; j<=4; j++)
			sum += a[i][j]%2;
	printf("%d\n", sum);
	for(int i=1; i<=4; i++)
		for(int j=1; j<=4; j++)
			if(a[i][j]%2)
				printf("%d %d\n", i, j);
	return 0;
} 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115438.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号