POJ 2965 The Pilots Brothers' refrigerator(DFS)

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

题目链接

DFS暴力深搜，这道题目只比POJ 1753 Flip Game(DFS)多输出了每一步的选择情况，用一个数组在改变时记录一下改变情况最后输出即可。

AC代码:

//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <cstdlib>
#include <sstream>
#include <set>
#include <map>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+5;
const double eps = 1e-5;
const double e = 2.718281828459;

int ans = INF;
int temp_x, temp_y;
char input_maze[5][5];
bool suc_flag = 0;
bool maze[5][5];
int line[20][2];

bool suc_judge() {
    for (int i = 1; i < 5; ++i) {
    	for (int j = 1; j < 5; ++j) {
    		if (!maze[i][j]) {
    			return 0;
			}
		}
	}
	return 1;
}

void change(int x, int y) {
	for (int i = 1; i < 5; ++i) {
		maze[x][i] = !maze[x][i];
	}
	for (int i = 1; i < 5; ++i) {
		if (i == x) {
			continue;
		}
		maze[i][y] = !maze[i][y];
	}
}

void dfs(int x, int y, int step, bool flag) {
	if (flag) {
		line[step][0] = temp_x;
		line[step][1] = temp_y;
	}
	temp_x = x, temp_y = y;
	if (suc_judge()) {
		if (step < ans) {
			ans = step;
			suc_flag = 1;
		}
		return;
	}
	if (x > 4 || y > 4 || suc_flag) {
		return;
	}
	change(x, y);
	if (y == 4) {
		dfs(x + 1, 1, step + 1, 1);
		if (suc_flag) {
			return;
		}
		change(x, y);
		dfs(x + 1, 1, step, 0);
	}
	else {
		dfs(x, y + 1, step + 1, 1);
		if (suc_flag) {
			return;
		}
		change(x, y);
		dfs(x, y + 1, step, 0);
	}
	if (suc_flag) {
		return;
	}
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    mem(line, -1);
    for (int i = 1; i < 5; ++i) {
    	for (int j = 1; j < 5; ++j) {
    		cin >> input_maze[i][j];
    		maze[i][j] = input_maze[i][j] == '-' ? 1 : 0;
		}
	}
	dfs(1, 1, 0, 0);
	cout << ans << endl;
	for (int i = 1; i <= ans; ++i) {
		cout << line[i][0] << " " << line[i][1] << endl;
	}
    return 0;
}