POJ 1753

BFS位运算

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int map[6][6];int change[16] = { 51200, 58368, 29184, 12544, 35968, 20032, 10016, 4880, 2248,        1252, 626, 305, 140, 78, 39, 19 };int BFS(int state) {    queue
         
          
            > Q; Q.push(make_pair(state, 0)); int tmp; pair
           
             cur; int vis[65536] = { 0 }; while (!Q.empty()) { cur = Q.front(); Q.pop(); for (int i = 0; i < 16; i++) { tmp = cur.first ^ change[i]; if (tmp == 0 || tmp == 65535) return cur.second + 1; if (!vis[tmp]) Q.push(make_pair(tmp, cur.second + 1)), vis[tmp] = 1; } } return -1;}int main() {// freopen("data.txt", "r", stdin); char tmp; while (~scanf("%c", &tmp)) { int state = 0; memset(map, 0, sizeof(map)); map[1][1] = (tmp == 'b') ? 1 : 0; if (map[1][1]) state += 1; for (int i = 1; i < 4; i++) { scanf("%c", &tmp); map[1][i] = (tmp == 'b') ? 1 : 0; if (map[1][i]) state += 1 << i; } for (int i = 2; i <= 4; i++) { getchar(); for (int j = 1; j <= 4; j++) { scanf("%c", &tmp); map[i][j] = (tmp == 'b') ? 1 : 0; if (map[i][j]) state += 1 << ((i - 1) * 4 + j - 1); } } getchar(); if (state == 0 || state == 65535) { puts("0"); continue; } int ans = BFS(state); ans == -1 ? puts("Impossible") : printf("%d\n", ans); } return 0;}
           
          
         
        
       
      
     

 

POJ 2965

要求输出操作方式，DFS迭代加深。

#include 
     
      #include 
      
       using namespace std;int chess;int step;bool flag = 0;int ans[16];int flip[16] = { 0x111f, 0x222f, 0x444f, 0x888f, 0x11f1, 0x22f2, 0x44f4, 0x88f8,        0x1f11, 0x2f22, 0x4f44, 0x8f88, 0xf111, 0xf222, 0xf444, 0xf888 };void dfs(int bit, int deep) {    if (deep == step) {        flag = (chess == 0) ? 1 : 0;        return;    }    if (flag || bit > 15)        return;    ans[deep] = bit;    chess ^= flip[bit];    dfs(bit + 1, deep + 1);    chess ^= flip[bit];    dfs(bit + 1, deep);}int main() {//    freopen("data.txt", "r", stdin);    char tmp;    chess = 0;    for (int i = 0; i < 4; i++) {        for (int j = 0; j < 4; j++) {            scanf("%c", &tmp);            if (tmp == '+')                chess ^= (1 << (i * 4 + j));        }        if (i < 3)            getchar();    }    for (step = 0;; step++) {        dfs(0, 0);        if (flag)            break;    }    printf("%d\n", step);    for (int i = 0; i < step; i++)        printf("%d %d\n", ans[i] / 4 + 1, ans[i] % 4 + 1);    return 0;}