题目大意:将题中所给的图翻转成
----
----
----
----的状态,求需要多少步??
翻转规则是:
1)你可以翻转任何一个棋子
2)该棋子所在的航和列也会跟着翻转。
解题思路:本题和1753的思路很像。。都是使用暴力+DFS+ 枚举,但翻转规则和判断方法有所改变,并且需要记录下路径。
1)判断规则变成
bool judge_all(){ int i,j; for(i = 1 ; i < 5 ; ++i){ for(j = 1 ; j < 5 ; ++j){ if( chess[i][j] != false){ return false; } } } return true; }
2)翻转规则变成
/** * 翻转规则是:将自己及其所在行、所在列的棋子都翻转 */ void flip(int row ,int col){ int i; for(i = 1 ; i < 5 ; ++i){ chess[row][i] = !chess[row][i]; } for(i = 1 ; i < 5 ; ++i){ chess[i][col] = !chess[i][col]; } //因为上面chess[row][col]这个棋子翻转了两次,变回了原样,所以这里还要再翻转一次 chess[row][col] = !chess[row][col]; }
3)需要在翻转时记录路径
flip(row,col); r[deep] = row;//记录路径的横坐标 c[deep] = col;//记录路径的纵坐标
代码如下:
/* * 2965_1.cpp * * Created on: 2013年9月13日 * Author: Administrator */ #include <iostream> #include <cstdio> using namespace std; bool chess[6][6] = {false}; bool flag ; int step; int r[20]; int c[20]; bool judge_all(){ int i,j; for(i = 1 ; i < 5 ; ++i){ for(j = 1 ; j < 5 ; ++j){ if( chess[i][j] != false){ return false; } } } return true; } /** * 翻转规则是:将自己及其所在行、所在列的棋子都翻转 */ void flip(int row ,int col){ int i; for(i = 1 ; i < 5 ; ++i){ chess[row][i] = !chess[row][i]; } for(i = 1 ; i < 5 ; ++i){ chess[i][col] = !chess[i][col]; } //因为上面chess[row][col]这个棋子翻转了两次,变回了原样,所以这里还要再翻转一次 chess[row][col] = !chess[row][col]; } void dfs(int row , int col , int deep){ if(deep == step){ flag = judge_all(); return ; } if(flag || row == 5){ return ; } flip(row,col); r[deep] = row;//记录路径的横坐标 c[deep] = col;//记录路径的纵坐标 if(col < 4){ dfs(row,col+1,deep+1); }else{ dfs(row+1,1,deep+1); } flip(row,col); if(col<4){ dfs(row,col+1,deep); }else{ dfs(row+1,1,deep); } } int main(){ int i,j; char temp; flag = false; for(i = 1 ; i < 5 ; ++i){ for(j = 1 ; j < 5 ; ++j){ cin >> temp; if(temp == '+'){ chess[i][j] = true; } } } for(step = 0 ; step <= 16 ; ++step){ dfs(1,1,0); if(flag){ break; } } cout<<step<<endl; for(i = 0 ; i < step ; ++i){ cout<<r[i]<<" "<<c[i]<<endl; } }