http://poj.org/problem?id=2965
跟POJ1753相似，暴力枚举。我这里用了迭代加深。
#include <stdio.h>
#include <string.h>
int chess;
int step, flag;
int row[20], col[20];
inline void flip(int pos) {
chess = chess^(1<<pos);
for(int i=0; i<4; ++i)
chess=chess^(1<<(pos/4*4 + i));
for(int i=0; i<4; ++i)
chess=chess^(1<<(pos%4 + i*4));
}
void dfs(int pos,int k) {
if(k==step) {
flag = (chess==0xFFFF);
return ;
}
if(flag || pos>15) return;
row[k] = pos/4;
col[k] = pos%4;
flip(pos);
dfs(pos+1, k+1);
flip(pos);
dfs(pos+1, k);
}
int main() {
int i,j;
char temp[5];
chess = 0;
for(i=0; i<4; ++i) {
scanf("%s",&temp);
for(j=0; j<4; ++j)
if(temp[j]=='-')
chess = chess^(1<<(i*4+j));
}
flag = 0;
for(step=0; step<=16; step++) { //迭代搜索深度
dfs(0,0);
if(flag)
break;
}
printf("%d\n",step);
for(i=0; i<step; ++i)
printf("%d %d\n",row[i]+1,col[i]+1);
return 0;
}