POJ 2965 The Pilots Brothers' refrigerator

2023-11-21 21:18

本文主要是介绍POJ 2965 The Pilots Brothers' refrigerator,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

  题意:想把大象装冰箱,但是呢,有的门是开(-)着的,有的是关(+)着的,必须所有的门都打开才能把大象装进去,但是你想开一个门的时候,它所在的行和它所在的列都会发生翻转,(本来是开,变成关,是关的变成开)。

  思路:其实这个题和POJ1753是一样的,这个题多了一个输出路径,加两个数组记录一下就行了,4*4的门一共16个,最多不会超过16步,用深搜完全可以,对于一个门,无非就两种情况,你翻转他或者跳过他,翻转过后,发现不合适,怎么办,在反转一次,因为翻转偶数次会恢复到原来状态。

附上代码:

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char map[5][5];
int mix;
int tx[30],ty[30]; //记录临时路径
int ansx[30],ansy[30];//最少步数时的路径
int check()//检查门是否全部打开
{for(int i=0; i<4; i++)for(int j=0; j<4; j++)if(map[i][j]!='-')return 0;return 1;
}
void turn (int x,int y) //翻转一行和一列
{//翻转一个点奇数次才能改变他的状态,偶数次不会改变if(map[x][y]=='-')map[x][y]='+';else map[x][y]='-';for(int i=0; i<4; i++){if(map[x][i]=='-')map[x][i]='+';else map[x][i]='-';}for(int i=0; i<4; i++){if(map[i][y]=='-')map[i][y]='+';else map[i][y]='-';}
}
void dfs(int x,int y,int step)
{if(check()){if(mix>step){mix=step;//记录最小步数for(int i=0; i<step; i++)//把路径记录下来,方便输出{ansx[i]=tx[i];ansy[i]=ty[i];}}return ;}if(x==4||step>16) return ;//一共四行从0-3,4*4最多16步turn(x,y);//翻转这个点tx[step]=x;ty[step]=y;if(y==3)dfs(x+1,0,step+1);else dfs(x,y+1,step+1);turn(x,y);//不翻转这个点的话要再翻回来,相当于回溯if(y==3)dfs(x+1,0,step);else dfs(x,y+1,step);
}
int main()
{int i,j;mix=9999;for(i=0; i<4; i++)scanf("%s",map[i]);dfs(0,0,0);printf("%d\n",mix);for(i=0; i<mix; i++)printf("%d %d\n",ansx[i]+1,ansy[i]+1);return 0;
}

下面是一个大神的思路,ORZ,大家可以参考一下:

证明:要使一个为'+'的符号变为'-',必须其相应的行和列的操作数为奇数;可以证明,如果'+'位置对应的行和列上每一个位置都进行一次操作,则整个图只有这一'+'位置的符号改变,其余都不会改变.设置一个4*4的整型数组,初值为零,用于记录每个点的操作数,那么在每个'+'上的行和列的的位置都加1,得到结果模2(因为一个点进行偶数次操作的效果和没进行操作一样,这就是楼上说的取反的原理),然后计算整型数组中一的
个数即为操作数,一的位置为要操作的位置(其他原来操作数为偶数的因为操作并不发生效果,因此不进行操作)
*********************************
此上证其可以按以上步骤使数组中值都为‘-’
********************************
在上述证明中将所有的行和列的位置都加1后,在将其模2之前,对给定的数组状态,将所有的位置操作其所存的操作数个次数,举例,如果a[i][j]==n,则对(i,j)操作n次,当所有的操作完后,即全为‘-’的数组。
其实就是不模2的操作,作了许多的无用功。
以上的操作次序对结果无影响,如果存在一个最小的步骤,则此步骤一定在以上操作之中。(简单说下:因为以上操作已经包含了所有可改变欲改变位置的操作了)
而模2后的操作是去掉了所有无用功之后的操作,此操作同样包含最小步骤。
但模2后的操作去掉任何一个或几个步骤后,都不可能再得到全为‘-’的。(此同样可证明:因为操作次序无影响,先进行最小步骤,得到全为‘-’,如果还剩下m步,则在全为‘-’的数组状态下进行这m步操作后还得到一个全为
‘-’的数组状态,此只能是在同一个位置进行偶数次操作,与前文模2后矛盾,所以m=0),因此模2后的操作即为最小步骤的操作。
代码:

#include<stdio.h>
#include<string.h>
char map[5][5];
int ansx[30],ansy[30],mark[5][5];
int main()
{int i,j,k;for(i=0; i<4; i++)scanf("%s",map[i]);for(i=0; i<4; i++)for(j=0; j<4; j++)if(map[i][j]=='+'){mark[i][j]=!mark[i][j];for(k=0; k<4; k++){mark[i][k]=!mark[i][k];mark[k][j]=!mark[k][j];}}int num=0;for(i=0; i<4; i++)for(j=0; j<4; j++){if(mark[i][j]){ansx[num]=i;ansy[num++]=j;}}printf("%d\n",num);for(i=0; i<num; i++)printf("%d %d\n",ansx[i]+1,ansy[i]+1);return 0;
}

这篇关于POJ 2965 The Pilots Brothers' refrigerator的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/405151

相关文章

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离,求来回到点1的最短路中的边权和。 因为边很大,不能用原来的dijkstra什么的,所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码: #include<stdio.h>#include<stack>using namespace std;const int M

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];

poj 2349 Arctic Network uva 10369(prim or kruscal最小生成树)

题目很麻烦,因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚,不适合新手。自己写一个。 题意:给你点的坐标,然后两点间可以有两种方式来通信:第一种是卫星通信,第二种是无线电通信。 卫星通信:任何两个有卫星频道的点间都可以直接建立连接,与点间的距离无关; 无线电通信:两个点之间的距离不能超过D,无线电收发器的功率越大,D越大,越昂贵。 计算无线电收发器D

poj 1502 MPI Maelstrom(单源最短路dijkstra)

题目真是长得头疼,好多生词,给跪。 没啥好说的,英语大水逼。 借助字典尝试翻译了一下,水逼直译求不喷 Description: BIT他们的超级计算机最近交货了。(定语秀了一堆词汇那就省略吧再见) Valentine McKee的研究顾问Jack Swigert,要她来测试一下这个系统。 Valentine告诉Swigert:“因为阿波罗是一个分布式共享内存的机器,所以它的内存访问

uva 10061 How many zero's and how many digits ?(不同进制阶乘末尾几个0)+poj 1401

题意是求在base进制下的 n!的结果有几位数,末尾有几个0。 想起刚开始的时候做的一道10进制下的n阶乘末尾有几个零,以及之前有做过的一道n阶乘的位数。 当时都是在10进制下的。 10进制下的做法是: 1. n阶位数:直接 lg(n!)就是得数的位数。 2. n阶末尾0的个数:由于2 * 5 将会在得数中以0的形式存在,所以计算2或者计算5,由于因子中出现5必然出现2,所以直接一

poj 3159 (spfa差分约束最短路) poj 1201

poj 3159: 题意: 每次给出b比a多不多于c个糖果,求n最多比1多多少个糖果。 解析: 差分约束。 这个博客讲差分约束讲的比较好: http://www.cnblogs.com/void/archive/2011/08/26/2153928.html 套个spfa。 代码: #include <iostream>#include <cstdio>#i