POJ 2965(dfs,法則)

タイトルリンク:http://poj.org/problem?id=2965
1つの冷蔵庫に4*4の計16個のスイッチがあり、いずれかのスイッチの状態を変える(すなわち、スイッチがオフになり、スイッチがオンになる)と、このスイッチの同じ行、同じ列のすべてのスイッチが自動的に状態を変える.冷蔵庫を開けるには、すべてのスイッチを入れなければなりません.
     入力:1つ4×4の行列、+は閉じる、-は開く;
　  出力:冷蔵庫を開くのに必要な最小限の操作回数と、操作したスイッチ座標.
dfs

#include<iostream>
using namespace std;
bool board[16];
int is[16]; int js[16];
bool check(){
	for(int i=0;i<16;i++)
		if(!board[i]) return false;
	return true;
}
void init(){
	char a;
	for(int i=0;i<16;i++){
		cin>>a;
		if(a == '+') board[i] = 0;
		else board[i] = 1;
	}
}
void flip(int pos) {//flip
	int i = pos/4;
	int j = pos%4;
	board[pos] = !board[pos];
	for(int m=0;m<4;m++){
		board[i*4+m] = !board[i*4+m]; // row flip
		board[m*4+j] = !board[m*4+j]; // flip column
	}
}
bool dfs(int pos,int step){
	if(check()){
		cout<<step<<endl;
		for(int i=0;i<step;i++)
			cout<<is[i]<<" "<<js[i]<<endl;
		return true;
	}
	if(pos >= 16) return false;
	if(dfs(pos+1,step)) return true;
	flip(pos);
	is[step] = pos/4 + 1; // sign the road;
	js[step] = pos%4 + 1;
	if(dfs(pos+1,step+1)) // after flip 's dfs
		return true;
	flip(pos); // backtracking;
	return false;
}
int main(){
	init();
	dfs(0,0);
}

法則、直接1つの比較的に良い解析を貼りましょう.
http://www.cnblogs.com/Java-tp/p/3873557.html