POJ2965
题意分析:
有个4*4的0/1图,初始状况是随机的。每次可以选16个位置中的一个位置翻,每翻一次,该位置所在的行和列的所有值都被取反,问要至少翻几次才能把它翻成全是减号。
和POJ1753类似,这里用的dfs+回溯法写的,先把格子转换成0/1图,然后dfs即可。
2019年2月23日
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define maxn 10010
using namespace std;
char ch;
int mp[maxn][maxn],ansx[maxn],ansy[maxn],x[maxn],y[maxn];
int ans=33;void flip(int ss){
int tx=ss/4;int ty=ss%4;for(int i=0;i<4;i++){
mp[tx][i]=1-mp[tx][i];mp[i][ty]=1-mp[i][ty];}mp[tx][ty]=1-mp[tx][ty]; //被重复翻了2次
}bool complete(){
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(mp[i][j]==1) return false;}}return true;
}
//s表示当前处理的格子,b表示翻转的次数
void dfs(int s,int b){
if(complete()){
if(ans>b){
//最多翻转33次ans=b;for(int i=1;i<=ans;i++){
ansx[i]=x[i];ansy[i]=y[i];}return ;}}if(s>=16) return ;dfs(s+1,b);flip(s);x[b+1]=s/4+1;y[b+1]=s%4+1;dfs(s+1,b+1);flip(s); //回溯
}
int main(){
std::ios::sync_with_stdio(false);for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
cin>>ch;if(ch=='+'){
mp[i][j]=1;}else if(ch=='-') {
mp[i][j]=0;}}}dfs(0,0);cout<<ans<<endl;for(int i=1;i<=ans;i++){
cout<<ansx[i]<<" "<<ansy[i]<<endl;}return 0;
}
dfs+回溯:
#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
int x[20],y[20]; //临时路径
int ansX[20],ansY[20]; //最终路径
int ans=33; //最多翻转33次int mp[5][5];
void init(){
char ch;for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
cin>>ch;if(ch=='-') mp[i][j]=1;else mp[i][j]=0;}}
}bool complete(){
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(mp[i][j]==0) return false;}}return true;
}
void flip(int s){
int x1=s/4;int y1=s%4;for(int i=0;i<4;i++){
mp[i][y1]=!mp[i][y1];mp[x1][i]=!mp[x1][i];}mp[x1][y1]= !mp[x1][y1];
}
void dfs(int s,int b){
//s代表当前处理的格子,b代表翻转格子次数if(complete()){
if(ans>b){
//最多翻转an=33次ans=b;for(int i=1;i<=ans;i++){
ansX[i]=x[i];ansY[i]=y[i];}return ;}}if(s>=16) return ;dfs(s+1,b); //不管第s个格子,直接向下找flip(s); //翻转第s个格子x[b+1]=s/4+1; //临时路径y[b+1]=s%4+1;dfs(s+1,b+1);flip(s); //回溯
}int main(){
init();dfs(0,0);cout<<ans<<endl;for(int i=1;i<=ans;i++){
printf("%d %d\n",ansX[i],ansY[i]);}return 0;
}