背景：和poj1753一样，用dfs就可以做出来，只是和1753相比较得输出一些步骤，，不过这也不麻烦，直接用两个数组就可以存储了。不过记住当递归回来的时候记住把数组里面对应位置的元素清零。
思路：同上一篇1753.
#include <stdio.h>#include <string.h>int q[4][4],ok=0,r[16],c[16];int iswin(void){for(int i=0;i<4;i++)for(int j=0;j<4;j++)if(q[i][j]!=1) return 0;return 1;}void change(int i,int j){q[i][j]=!q[i][j];for(int k=0;k<4;k++){q[i][k]=!q[i][k];q[k][j]=!q[k][j];}}void dfs(int m,int sum,int a,int b){if(ok) return;else if(m==sum){if(iswin()){ok=1;printf("%d\n",sum);for(int k=0;k<sum;k++)printf("%d %d\n",r[k],c[k]);}else return;}else{for(int i=a;i<4;i++){for(int j=b;j<4;j++){r[m]=i+1;c[m]=j+1;change(i,j);if(j<3) dfs(m+1,sum,i,j+1);else {dfs(m+1,sum,i+1,0);b=0;}change(i,j);r[m]=0;c[m]=0;}}return;}}int main(void){char ch;memset(r,0,sizeof(r));memset(c,0,sizeof(c));for(int i=0;i<4;i++)for(int j=0;j<4;j++){scanf("%c",&ch);if(j==3) getchar();q[i][j]=(ch=='+')?0:1;}if(iswin()) {printf("%d\n",0);return 0;}for(int k=1;k<=16;k++){dfs(0,k,0,0);if(ok) break;}return 0;}
在网上看到有这样用递归的，感觉好高大上。
虽然他写的代码，我有一些地方不懂，不过这些都是我要学习的东西。
他的思路：
1.一个元素翻转奇数次状态不变,翻转偶数次状态改变
由1容易推到出2
2:要想把第Sij翻转,同时保持第i行和第j列其他元素状态不变,sij本身翻转两次,第i和第j列的其他元素翻转一次.
由把所有状态为关的元素都做一次2操作,记录那些元素状态变化过,变化过的元素个数即最小步骤数.
由以上分析得出,各个元素的步骤顺序其实是无所谓的.把变化的过元素按任意顺序输出即步骤.
附代码:
#include <iostream> #include <queue> bool mark[4][4]; struct Pos {int x;int y; }; std::queue<Pos> Ans; int input() {memset(mark,0,sizeof(mark));int i ,j,k;char ch;for (i = 0 ;i < 4 ; ++ i){for (j = 0 ;j < 4 ; ++j){ch = getchar();if ('+' == ch){mark[i][j] = !mark[i][j];for(k = 0 ; k < 4 ; k ++){mark[i][k] = !mark[i][k];mark[k][j] = ! mark[k][j];}}}getchar();}return 0; } int main() {int nStep = 0;int i,j;input();for ( i = 0 ; i < 4; ++i){for (j = 0 ; j < 4 ; ++j){if (mark[i][j]){nStep ++;Pos pos;pos.x = i + 1;pos.y = j + 1;Ans.push(pos);}}}std::cout <<nStep<<std::endl;while (!Ans.empty()){Pos pos = Ans.front();Ans.pop();std::cout<<pos.x<<" "<<pos.y<<std::endl;}return 0; }
人，总是很难改正自己的缺点，
