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)


相关推荐

  • bigtable是什么_BigTable

    bigtable是什么_BigTableBigtable是一个用来管理结构化数据的分布式存储系统,具有很好的伸缩性,能够在几千台应用服务器上处理PB数量级数据。谷歌有许多项目都把数据存储在Bigtable中,包括webindexing,G

  • 推荐几款流行的开源报表工具[通俗易懂]

    推荐几款流行的开源报表工具[通俗易懂]转自:http://www.anyrt.com/blog/sourcereport.html1.JasperReportJasperReport是最流行的开源报表工具之一,基于GPL开源许可协议,完全采用java编写,支持多种数据源,可打印或导出多种文件格式,支持PDF、HTML、XLS、CSV和XML文件输出格式。JasperReport也包含多个组件:JasperR…

    2022年10月20日
  • swagger使用「建议收藏」

    swaggerrestfuldemo网络上swagger的配置,大多都是复制粘贴转发的。本人开始的时候参照了配置过,基本都是以失败告终。一怒之下,造死了搞,搭建了一个swagger描述的rest风格的接口demo工程。使用的版本号为spring4+jdk8+swagger0.8.4搭建过程中遇到不少问题,主要是swagger默认依赖的是spring3.与jdk8配合的时候,有点问题。直接将s

  • 引用类型的一些方法

    引用类型的一些方法

  • 音频数字化简单原理「建议收藏」

    音频数字化简单原理     从字面上来说,数字化(Digital)就是以数字来表示,例如用数字去记录一张桌子的长宽尺寸,各木料间的角度,这就是一种数字化。跟数位常常一起被提到的字是模拟(Analog/Analogue),模拟的意思就是用一种相似的东西去表达,例如将桌子用传统相机将三视图拍下来,就是一种模拟的记录方式。两个概念:1、分贝(dB):声波振幅的度量单位,非

  • 谈谈5G的信道编码方法

    谈谈5G的信道编码方法最近因为联想的投票引发了轩然大波,让我们不得不审视一下投票的对象:5G的信道编码方式。信道编码是通信技术中非常关键的技术,用于对抗信道上的噪声以及干扰,提高传输的效率。我在通信技术的四大金刚一文中,按重要性将编码技术归为第二位,其中就包含了信道编码。不过,信道编码的效果是有极限的,这就是香农定理所指出的编码极限。在GSM系统中,采用了卷积以及交织等信道编码方式,离编码极限还有一段距…

发表回复

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

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