#include<iostream>
#include<cstdio>
#include<queue>

using namespace std;

struct Node {
    int cur_state;
    int step;
    int last_state;
};

bool visited[65537];

int path[65536];  //record path
int pathp[65536]; //record path pos

int change[16] = { // 16 status change
    0xf888,0xf444,0xf222,0xf111,
    0x8f88,0x4f44,0x2f22,0x1f11,
    0x88f8,0x44f4,0x22f2,0x11f1,
    0x888f,0x444f,0x222f,0x111f
};

//save each node to visit in queue
int bfs(int state){
    int i;
    Node cur,next;
    for(i=0;i<65536;i++)
        visited[i]=false;
    queue<Node> q;

    cur.cur_state = state;
    cur.step = 0;

    q.push(cur);
    visited[state] = true;
    path[state]=-1;


    while(!q.empty()){
        cur = q.front();
        q.pop();
        if( cur.cur_state == 65535){
            return cur.step;
        }

        for(i=0;i<16;i++){
            next.cur_state = cur.cur_state^change[i];

            if(visited[next.cur_state])
                continue;

            next.step = cur.step+1;


            path[next.cur_state] = cur.cur_state;
            pathp[next.cur_state] = i;
            
            if( next.cur_state == 65535){
                return next.step;
            }
            visited[next.cur_state]=true;
            q.push(next);

            //printf("%x\n",cur.cur_state);
        }
    }

    return -1;
}


void print_path(int state){
    int next_state = path[state];
    if(path[state] <0){
        return;
    }
    print_path(next_state);
    printf("%d %d\n",pathp[state]/4+1,pathp[state]%4+1);
}

int main(){
    int i,j,state,an;
    char ch,cn;
    cn=0;
    state=0;

    for(i=0;i<65536;i++)
    {
        path[i]=-1;
        pathp[i]=-1;
    }
    while((ch=getchar())!=EOF){
        if(ch == '-' || ch == '+'){
            cn++;
            state <<= 1;
            if(ch=='-'){
                state+=1;
            }
            if(cn == 16){
                an=bfs(state);

                if(an == -1)
                    printf("Impossible\n");
                else
                    printf("%d\n",an);

                /*
                i=65535;
                while(i>0){
                    printf("== %d %d %d\n",i,path[i],pathp[i]);
                    i=path[i];
                }*/
                print_path(65535);
                cn=0;
                state=0;
            }
        }
    }

    return 0;
}

• Re:bfs+位或，c++超时，g++过 (2) _xcc_ 2019-07-26 09:58:00