首页 > 代码库 > POJ - 2965 - The Pilots Brothers' refrigerator （高效贪心！！）
POJ - 2965 - 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
看着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;
}
POJ - 2965 - The Pilots Brothers' refrigerator （高效贪心！！）