思维

1、POJ 3279 Fliptile

参考：《挑战程序设计竞赛》P154

#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>#include <queue>#include <vector>#include <stack>#include <map>#include <set>#include <cmath>#include <cctype>#include <ctime>#include <cassert>using namespace std;#define REP(i, n) for (int i = 0; i < (n); ++i)#define eps 1e-9typedef long long ll;typedef pair<int, int> pii;const int INF = 0x7fffffff;const int maxn = 15;int N, M, t, i_t, x, y, Min = INF, cnt = 0;bool flag = true, have_sloution = false;int G[maxn][maxn], G_t[maxn][maxn], ans_t[maxn][maxn], ans[maxn][maxn];int dir[][2] = {{0, 0}, {1, 0}, {0, 1}, {0, -1}};int main() {#ifdef __AiR_H    freopen("in.txt", "r", stdin);//    freopen("out.txt", "w", stdout);#endif // __AiR_H    scanf("%d %d", &M, &N);    REP(i, M) REP(j, N) { scanf("%d", &G[i][j]); }    t = 1 << N;    REP(i, t) {        memcpy(G_t, G, sizeof(G_t));        memset(ans_t, 0, sizeof(ans_t));        i_t = i; cnt = 0;        flag = true;        for (int j = N - 1; j >= 0; --j) {            if (i_t & 1) {                ans_t[0][j] = 1; ++cnt;                if (cnt > Min) { flag = false; break; }                REP(k, 4) {                    x = dir[k][0]; y = j + dir[k][1];                    if (0 <= x && x < M && 0 <= y && y < N) { G_t[x][y] = !G_t[x][y]; }                }            }            i_t >>= 1;        }        if (!flag) { continue; }        for (int a = 1; a < M; ++a) REP(b, N) {            if (G_t[a - 1][b]) {                ans_t[a][b] = 1; ++cnt;                if (cnt > Min) { flag = false; break; }                REP(c, 4) {                    x = a + dir[c][0]; y = b + dir[c][1];                    if (0 <= x && x < M && 0 <= y && y < N) { G_t[x][y] = !G_t[x][y]; }                }            }        }        if (!flag) { continue; }        REP(j, N) { if (G_t[M - 1][j] == 1) { flag = false; break; } }        if (flag) {            have_sloution = true;            if (cnt < Min) { Min = cnt; memcpy(ans, ans_t, sizeof(ans)); }        }    }    if (!have_sloution) { PRintf("IMPOSSIBLE/n"); }    else {        for (int i = 0; i < M; ++i) {            for (int j = 0; j < N - 1; ++j) {                printf("%d ", ans[i][j]);            }            printf("%d/n", ans[i][N - 1]);        }    }#ifdef __AiR_H    printf("Time used = %.2fs/n", (double)clock() / CLOCKS_PER_SEC);#endif // __AiR_H    return 0;}