原题POJ2965
| Time Limit: 1000MS | Memory Limit: 65536K | |||
| Total Submissions: 21431 | Accepted: 8274 | 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
|
1 2 3 4 |
-+-- ---- ---- -+-- |
Sample Output
|
1 2 3 4 5 6 7 |
6 1 1 1 3 1 4 4 1 4 3 4 4 |
Source
这一道题跟POJ1753很相似， 两者都是枚举相关的算法， 完整代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#include <iostream> using namespace std; #include <stdio.h> int handle[4][4]; int x[32], y[32]; //temporary path int ansX[32], ansY[32] ; // final path int maxx= 33; void build() { int i, j; char c; for(i = 0; i < 4; i++) for( j = 0; j < 4; j++) { cin >> c; if( c == '+') handle[i][j] = 0; else handle[i][j] = 1; } } void flip(int s) { int i = s/4, j = s%4; for(int m = 0; m < 4; m++) { handle[i][m] = !handle[i][m]; handle[m][j] = !handle[m][j]; } handle[i][j] = !handle[i][j]; } int complete() { for(int i = 0; i < 4; i++) for(int j = 0; j < 4; j++) if(handle[i][j] == 0) return 0; return 1; } void dfs(int id, int num) { if(complete()) { if(maxx > num) { maxx = num; for(int i = 0; i < maxx; i++) { ansX[i] = x[i]+1; ansY[i] = y[i]+1; } } return ; } if(id >= 16) return ; dfs(id+1, num); flip(id); x[num] = id/4; y[num] = id%4; dfs(id+1, num+1); flip(id); } int main() { build(); dfs(0, 0); printf("%dn", maxx); for(int i =0; i < maxx; i++) { printf("%d %dn", ansX[i], ansY[i]); } return 0; } |
大部分功能函数都与POJ1753的一样， 最主要的有两个地方， 第一个这个题目要求输出路径， 所以必须用先用一个数组把临时路径存储下来， 然后最后再用一个数组输出最短路径， 这里当时自己没有理解透彻DFS算法， 居然还半天没想过来为什么要把临时路径存储下来而不直接complete过后就输出， 这里可以借用POJ1753里面所提到的那个逐步打印翻转的方法来理解， 模拟的结果：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
razrlele@OVO:~/build$ ./1753i wb bw 1 3 1 1 0 2 3 1 1 1 3 2 1 0 1 4 3 1 1 1 5 3 1 1 0 6 2 1 0 0 7 1 0 1 1 8 3 1 1 1 9 3 1 1 0 10 2 1 0 1 11 2 1 0 0 12 1 0 1 0 13 0 0 0 0 14 3 1 1 0 15 3 1 1 1 16 2 1 0 0 17 3 1 1 1 18 3 1 1 0 19 2 1 0 1 20 1 0 1 0 21 3 1 1 1 22 3 1 1 0 23 2 1 0 0 24 3 1 1 0 25 3 1 1 1 26 2 1 0 1 27 1 0 1 1 28 0 0 0 1 2 razrlele@OVO:~/build$ |
这里可以很清晰地看到， 在7和8次翻转过后， 虽然已经complete， 但是程序还没有遍历完， 依旧会继续运行下去， 所以这个时候必须把路径给存储好， 不然接下来就会被覆盖。
第二个就是临时路径存储操作应该放在哪里（现在回过头来看自己很低级， 但是当时确实昏了头），也可以从这个模拟的过程里面看出来每一次临时路径的存储操作应该放在第一个flip操作之后。
PS： 这道题目耗费我时间最长的地方其实是flip里面忘记翻转那个点自己， 也就是
|
1 |
handle[i][j] = !handle[i][j]; |
这一行代码， 然后就是各种抓狂为什么只会输出零。。。