http://poj.org/problem?id=1753 BFS + Bit fiddling

poj1753.cpp

#include <cstdio>
#include <queue>
#include <iostream>
#include <string>
#include <bitset>

using namespace std;

const int rows = 4, cols = 4;
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 || st.first == 0) {
            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 || st.first == 0) {
                        return st.second + 1;
                    }
                    q.push(pair<int, int>(s, st.second + 1));
                    visited.set(s);
                }
            }
        }
    }
    return ans;
}

void solve() {
    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] == 'b')
                status |= 1 << (i * cols + j);
        }
    }

	int res = sol(status);
    if (res >= 0)
        cout << res << endl;
    else
        cout << "Impossible" << endl;
}

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

1. 找最少的步数，使用BFS
2. 棋盘状态的压缩：使用4 * 4 = 16位的一个整数来表示，位操作。
3. 访问过的状态记录：bool数组？内存开销过大，使用bitset