黑白迷阵 http://ac.jobdu.com/problem.php?pid=1542

jobdu1542.cpp

#include <cstdio>
#include <queue>
#include <iostream>
#include <string>
#include <cstring>
#include <climits>

using namespace std;

const int rows = 4, cols = 5;
int dir[5][2] = {{0, 0}, {-1, 0}, {1, 0}, {0, 1}, {0, -1}};
int board[rows][cols];   // 棋盘: 0 - 白色，1 - 黑色
int flip[rows][cols];    // 是否翻转

int get_color(int i, int j) {
    int color = board[i][j];
    
    // 上下左右四个方向的棋子翻转都会影响当前棋子的状态
    for (int k = 0; k < 5; k++) {
        int ii = i + dir[k][0], jj = j + dir[k][1];
        if (ii >= 0 && ii < rows && jj >= 0 && jj < cols) {
            color += flip[ii][jj];
        }
    }
    color = color % 2;
    return color;
}

int get_steps() {
    // 根据第一行的翻转状态，从第二行开始枚举，看哪些需要翻转
    for (int i = 1; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            // 如果上一行的对应位置在之前所有翻转结束后是白色的
            // 那么本行相应位置的应做翻转
            if (get_color(i - 1, j) == 0) {
                flip[i][j] = 1;
            }
        }
    }
    
    // 最后一行应全为黑色才算正确
    for (int i = 0; i < cols; i++) {
        if (get_color(rows - 1, i) == 0) {
            return INT_MAX;
        }
    }
    
    int steps = 0;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            steps += flip[i][j];
        }
    }
    return steps;
}

int sol() {
    int max_num = 1<<cols;
    int min_steps = INT_MAX;
    
    // 枚举第一行的所有翻转状态，00000~11111，每一个整数代表第一行的一种状态
    // 每一位代表一个格子，0为不翻转，1为翻转
    for (int i = 0; i < max_num; i++) {
        memset(flip, 0, sizeof(flip));
        for (int j = 0; j < cols; j++) {
            int idx = cols - j - 1;
            flip[0][idx] = (i>>j) & 0x01;
        }
        
        int steps = get_steps();
        if (steps < min_steps) {
            min_steps = steps;
        }
    }
    return min_steps;
}

void solve() {
    // freopen("/Users/danglu/inputs/input.txt", "r", stdin);
    int T;
    cin >> T;
    while (T--) {
        for (int i = 0; i < rows; i++) {
            string str;
            cin >> str;
            for (int j = 0; j < str.length(); j++) {
                board[i][j] = str[j] - '0';
            }
        }
        int steps = sol();
        cout << steps << endl;
    }
}

int main() {
    solve();
    return 0;
}

jobdu1542_tle.cpp

#include <cstdio>
#include <queue>
#include <iostream>
#include <string>
#include <bitset>
#include <cstring>
 
using namespace std;
 
const int rows = 4, cols = 5;
const int max_num = 1<<(rows * cols);
int all_black = (max_num) - 1;
bitset<max_num+1> visited;
int dir[5][2] = {{0, 0}, {-1, 0}, {1, 0}, {0, 1}, {0, -1}};
 
int flip(int status, int x, int y) {
    for (int i = 0; i < 5; i++) {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
        if (xx >=0 && xx < rows && yy >=0 && yy < cols) {
            status ^= 1 << (xx * cols + yy);
        }
    }
    return status;
}
 
int sol(int status) {
    visited.reset();
    queue<pair<int, int> > q;
    q.push(pair<int, int>(status, 0));
    visited.set(status);
    int ans = -1;
     
    while (!q.empty()) {
        pair<int, int> st = q.front();
        q.pop();
        if (st.first == all_black) {
            ans = st.second;
            break;
        }
         
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int s = flip(st.first, i, j);
                if (!visited.test(s)) {
                    if (s == all_black) {
                        return st.second + 1;
                    }
                    q.push(pair<int, int>(s, st.second + 1));
                    visited.set(s);
                }
            }
        }
    }
    return ans;
}
 
void solve() {
    // freopen("/Users/danglu/inputs/input.txt", "r", stdin);
    int T;
    cin >> T;
    while (T--) {
        int status = 0;
        for (int i = 0; i < rows; i++) {
            string str;
            cin >> str;
            for (int j = 0; j < str.length(); j++) {
                if (str[j] == '1')
                    status |= 1 << (i * cols + j);
            }
        }
        //cout << status << endl;
         
        int res = sol(status);
        cout << res << endl;
    }
}
 
int main() {
    solve();
    return 0;
}

两种解法：

file	method	status
jobdu1542.cpp	DP	AC
jobdu1542_tle.cpp	BFS + 状态压缩	TLE

着重说下DP的解法：
1 枚举第一行的所有翻转状态的可能性，有2^5=32种可能。
2 对于第一行的每种翻转状态，第二行是否翻转取决于第一行翻转后的状态（使得第一行全黑），以此类推，每一行的每一个格子是否翻转取决于上一行翻转后的状态，即：

# 若当前棋子的上一行的对应棋子为白色，那么当前棋子必须翻转
flip[i][j] = 1 if color[i-1][j] is white else 0

3 往下递推，由第一行的每种翻转状态可以得到使得前N-1行都变黑的一个翻转方案，这个方案是否可行取决于第N行是否全黑。对于所有可行的状态，取得需要翻转棋子个数最小的那个。

呜呜呜

党大的总结就是科学啊
真漂亮，还有表格！

我的想法

暴力

1. 这道题其实暴力法也应该用DFS+递归+DP的，coding会短很多，简单很多。
2. 事实上暴力法应该是直接枚举算出2^20种棋盘格局可否翻转，以及翻转最少步数，把结果全都保存起来，然后接下来对于每个输入应该是直接查表的，不应该每次都重新算。
3. 空间可以用2^20个bit，然后如果有值的，放在hash表里，总的来讲空间也可以接受。

正解给我的启发

1. 记录棋盘状态的方法. 我以前从来没这么用过. 记录flip, 然后查询status, 非常科学.
2. 枚举第一行状态的方法. 对于64bit以内的用这个方法枚举再科学不过了. 我之前一直都是用递归dfs枚举的. 这个枚举方法还可以用在求短字符串的combination上
3. 核心的贪心法则: 我枚举完第一行, 接着可以不必枚举了. 以后很多问题都可以这样想想, 试试行不行得通.

哈哈 你这个总结很不错啊 我们公司程序员平时文档都用Markdown的

这道题其实暴力法也应该用DFS+递归+DP的，coding会短很多，简单很多。

DFS会快吗？我不大清楚诶 反正我BFS给超时了，我是看到最少俩字条件反射就顺手写了个BFS的 一开始还写错了 ==
我抽空写写

核心的贪心法则: 我枚举完第一行, 接着可以不必枚举了. 以后很多问题都可以这样想想, 试试行不行得通.

对，其它行的情况可以由棋子之间的制约关系得到，我刚开始也没转过弯来

DFS会快吗？

DFS: 2^20复杂度
正解的复杂度只有2^5 * 20
始终是会挂的，但挂得有态度 ;D