POJ 1753（枚举）

题目LINK

题意解释

题意大体是。初始状态用字符串录入棋盘的初始状态。然后问最少有几步能把棋盘全翻成白的或者黑的。

收获

这道题用的是枚举的方法，就是把所有可能的翻的顺序全翻一遍。递归是一行一行的入栈的，这么递归是这两个退出递归的条件，可以包含所有可能的翻的棋子。这道题卡我的地方还是在于对递归的理解。同时，在dfs函数中，如果用count++会出问题，应该用count+1。

AC代码

#include <iostream>
#include <string>

#define inf 9999999

using namespace std;

int map[4][4];
int ans = inf;
string str;

int judge(){ // judge if all black or all white
    int x = map[0][0];
    
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if(map[i][j] != x) return 0;
        }
    }
    return 1;
}

void flip(int x, int y){
    map[x][y] = !map[x][y];
    if(x - 1 >= 0)
        map[x-1][y] = !map[x-1][y];
    if(x + 1 < 4)
        map[x+1][y] = !map[x+1][y];
    if(y - 1 >= 0)
        map[x][y-1] = !map[x][y-1];
    if(y + 1 < 4)
        map[x][y+1] = !map[x][y+1];
}

int dfs(int x, int y,int count){
    if(judge()){
        if(ans > count)
            ans = count;
//        cout << "judge: " << judge() << endl;
//        cout << "count: " << count << endl;
        
        return 0;
    }
    
    if(x >= 4 || y >= 4){
        return 0;
    }
    
    int x_next, y_next;
    y_next = (y + 1) % 4;
    x_next = x + (y + 1) / 4;
    
    dfs(x_next, y_next, count);
    flip(x, y);
    
    dfs(x_next, y_next, count+1);//why count++ cannot work
    flip(x, y);
    
    return 0;
}

int main(void){
    for (int i=0; i<4; i++)
    {
        cin >> str;
        for (int j=0; j<4; j++){
            if (str[j]=='b'){
                map[i][j]=0;
            }
            else{
                map[i][j]=1;
            }
        }
    }
    
    
    dfs (0,0,0);
    if (ans == inf )
        printf ("Impossible\n");
    else printf ("%d\n",ans);
    return 0;
}