POJ 2965 The Pilots Brothers' refrigerator

题面

The game “The Pilots Brothers: following the stripy elephant” has a quest where a player needs to open a refrigerator.

There are 16 handles on the refrigerator door. Every handle can be in one of two states: open or closed. The refrigerator is open only when all handles are open. The handles are represented as a matrix 4х4. You can change the state of a handle in any location [i, j] (1 ≤ i, j ≤ 4). However, this also changes states of all handles in row i and all handles in column j.

The task is to determine the minimum number of handle switching necessary to open the refrigerator.

题意

给你一个4*4的01矩阵，每次可以选择一个位置，将这个位置所处的行，列上的每个点0变成1，1变成0，求出最少的操作数，并输出方案.

分析

刚看到这道题的时候无从入手，结果发现这只是4*4，那不直接暴力dfs！大水题 OvO 。下次遇到升级版该咋办……管他呢qwq

CODE

#include
#include
#include
#include
using namespace std;
#define inf 0x3f3f3f3f
char s[5][5];
int a[5][5];
int tot=inf;
struct node{
    int dx;
    int dy;
}now[26],ans[26];
bool check(){
    for(int i=1;i<=4;++i)
        for(int j=1;j<=4;++j)
            if(!a[i][j]) return 0;
    return 1;
}
void dfs(int x,int y,int cnt){
    if(x>4){
        if(check()&&cnt<tot){
            tot=cnt;
            for(int i=1;i<=cnt;++i)
                ans[i]=now[i];
        }
        return;
    }
    if(y>4) {
        dfs(x+1,1,cnt);
        return;
    }
    for(int i=1;i<=4;++i)
        a[x][i]^=1,a[i][y]^=1;
    a[x][y]^=1;
    now[cnt+1].dx=x,now[cnt+1].dy=y;
    dfs(x,y+1,cnt+1);
    for(int i=1;i<=4;++i)
        a[x][i]^=1,a[i][y]^=1;
    a[x][y]^=1;
    dfs(x,y+1,cnt);
    return;
}
int main(){
    for(int i=1;i<=4;++i)
        for(int j=1;j<=4;++j){
            scanf(" %c",&s[i][j]);
            if(s[i][j]=='-') a[i][j]=1;
        }
    dfs(1,1,0);
    printf("%d\n",tot);
    for(int i=1;i<=tot;++i)
        printf("%d %d\n",ans[i].dx,ans[i].dy);
    return 0;
}