黑白迷阵 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;
}

DFS会快吗？

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