Triangle War II (ZJU Sep 2008 contest)

ZOJ Problem Set - 3038

一开始以为是lights out这种puzzle,仔细看发现只能按unpushed button, 这是与lights out 类问题严重的不同，不是finite field。只好上brute force, 最多状态，2^21还是可行的，先试了DFS,发现stack overflow, 然后用BFS搞定，发生了一点小问题，visited忘了reset...

这道题里用bit operation很方便的。

• 首先把adj matrix表示成N个bit vector,每个bit vector是从一个结点出发的所有边。
• 同样将当前图的状态也表示成一个N位的bit vector (status, 1 表示unpushed, 0表示pushed)。
  
• 用bit vector i 同当前graph结点的状态 status 异或就直接得到push button i后的结点状态。

下面的code是查看当前graph结点i 是否是unpushed， 如果是则按下它得到之后的状态。

if(status &(1 << i))       
 status = status ^ adj[i];

#include <queue>
#include <ctime>
using namespace std;

// triangle size 
const int MAX_LEVEL = 6;

// node # in the triangle
const int MAX_N = (MAX_LEVEL+1)*(MAX_LEVEL)/2;

short visited[(1<<MAX_N)+1];
// adjancency matrix
int adj[MAX_N]; 
int n; // # of levels
int maxon; // max # of unpushed node

void construct_adj(int N) {
    memset(adj, 0, sizeof(adj));
    for(int level = 1; level <= n; ++level) {
        int i = level*(level-1)/2; // start point of this level
        for(int j = 0; j < level; ++j) {
            int a = i+j;
            adj[a] |= (1<<a); // self connected
            if(level < n) {
                adj[a] |= 1<<(a+level);   // connect with left child
                adj[a] |= 1<<(a+level+1); // connect with right child
            }
            if(j < level-1) adj[a] |= 1<<(a+1); // connect with right sibling
            if(j > 0)       adj[a] |= 1<<(a-1); // connect with left sibling
        }
    }
    // sysmetric filling
    for(int i = 1; i < N; ++i)
        for(int j = 0; j < i; ++j) {
             int t = adj[j] & (1<<(i));
             if(t) adj[i] |= 1<<j;
        }
    memset(visited, 0, sizeof(visited));
}

void checkmax(int &a, int b) {
    if(b > a) a = b;
}

// couting 1's
int count_bit(int n) {
    int bits = 0;
    while(n) {
        n &= n-1;
        ++bits;
    }
    return bits;
}



// bfs
int search(int status, int N) {
    visited[status] = 1;
    queue<int> Q;
    Q.push(status); 
    while(!Q.empty()) {
        int cur = Q.front();
        Q.pop();
        checkmax(maxon, count_bit(cur));
        if(maxon == N) break;
        if(!cur) continue;
        for(int i = 0; i < N; ++i) {
            if( cur & (1<<i)) {
                int dest = cur ^ adj[i];
                if(dest && !visited[dest]) {
                    visited[dest] = 1;
                    Q.push(dest);
                }
            } 
        }
    }
    return maxon;
}

int main() {

    //int start = clock();
    while(scanf("%d", &n) != EOF) {
        int N = n*(n+1)/2;
        construct_adj(N); // construct adj matrix

        int cells = 0;    // current cell status
        for(int level = 1; level <= n; ++level) {
            int i = level*(level-1)/2; // start point of this level
            for(int j = 0; j < level; ++j) {
                char b; // button status
                scanf(" %c", &b);
                if(b == '.') cells |= 1<< (i + j);
            }
        }
        maxon = -1;
        printf("%d\n", search(cells, N));
    }

   // printf("total time %d", clock()-start);
    return 0;
}