poj2965-poj2965-The Pilots Brothers' refrigerator

方法同poj1753，但用在这题就TLE了，以下是TLE版本：

  1#include <stdio.h>
  2#include <stdlib.h>
  3#include <string.h>
  4#define MAXSTATE 65536
  5#define MAXSIZE 16
  6#define ALLOPEN 0
  7
  8//队列结构体
  9typedef struct node{
 10    int data;
 11    struct node *next;
 12}NODE;
 13typedef struct{
 14    NODE *front;
 15    NODE *rear;
 16}QUEUE;
 17//全局变量
 18QUEUE queue;
 19int distance[MAXSTATE];
 20int position[MAXSTATE];
 21int parentState[MAXSTATE];
 22//入队列函数
 23void EnQueue(QUEUE *q, int d)
 24{
 25    NODE *newNode;
 26    newNode=(NODE *)malloc(sizeof(NODE));
 27    newNode->data=d;
 28    newNode->next=NULL;
 29    
 30    if(q->front!=NULL){
 31        q->rear->next=newNode;
 32        q->rear=newNode;
 33    }
 34    else
 35        q->front=q->rear=newNode;
 36}
 37//出队列函数
 38int DeQueue(QUEUE *q)
 39{
 40    int temp;
 41    NODE *oldNode;
 42    if(q->front==NULL){
 43        printf("List empty!\n");
 44        return -1;
 45    }
 46    oldNode=q->front;
 47    temp=q->front->data;
 48    q->front=q->front->next;
 49    free(oldNode);
 50    return temp;
 51}
 52//判断队列是否为空
 53int Empty(QUEUE *q){
 54    if(q->front==NULL)
 55        return 1;
 56    return 0;
 57}
 58
 59int ChangeState(int id, int pos)
 60{
 61    int t, new_id;
 62    new_id=id^1<<pos;
 63    if (pos>=4){
 64        t=pos-4;
 65        while(t>=0) {
 66            new_id^=1<<t;
 67            t-=4;
 68        }
 69    }
 70    if(pos<=11){
 71        t=pos+4;
 72        while(t<=15){
 73            new_id^=1<<t;
 74            t+=4;
 75        }
 76    }
 77    if(pos%4>0){//向左
 78        t=pos-1;
 79        while(t%4!=3 && t>=0){
 80            new_id^=1<<t;
 81            --t;
 82        }
 83    }
 84    if(pos%4<3){//向右
 85        t=pos+1;
 86        while(t%4!=0){
 87            new_id^=1<<t;
 88            ++t;
 89        }
 90    }
 91    return new_id;
 92}
 93
 94void Output(int stat)
 95{
 96    int cur_state, len=0, i;
 97    int arr_x[MAXSIZE];
 98    int arr_y[MAXSIZE];
 99    
100    cur_state=stat;
101    printf("%d\n", distance[cur_state]);
102    while(distance[cur_state]!=0){
103        arr_x[len]=position[cur_state]/4+1;
104        arr_y[len++]=position[cur_state]%4+1;
105        cur_state=parentState[cur_state];
106    }
107    for (i=len-1;i>=0;i--){
108        printf("%d %d\n", arr_x[i], arr_y[i]);
109    }
110}
111
112void main(int argc, char *argv[])
113{
114    char c;
115    int cur_state=0, new_state;
116    int i=0;
117    QUEUE *q;
118    q=&queue;
119    //freopen("input.txt", "r", stdin);
120    
121    while(scanf("%c", &c)!=EOF){
122        if(c!='\n'){
123            if (c=='+') cur_state += 1<<i;
124            i++;
125        }
126    }
127    memset(distance, -1, MAXSTATE*sizeof(int));
128    
129    if(cur_state==ALLOPEN){
130        printf("0\n");
131        return;
132    }
133    parentState[cur_state]=-1;
134    distance[cur_state]=0;
135    position[cur_state]=-1;
136    EnQueue(q, cur_state);
137    while(!Empty(q)){
138        cur_state=DeQueue(q);
139        for (i=0;i<MAXSIZE;i++){
140            new_state=ChangeState(cur_state, i);
141            if (new_state==ALLOPEN){//成功
142                parentState[new_state]=cur_state;
143                position[new_state]=i;
144                distance[new_state]=distance[cur_state]+1;
145                Output(new_state);
146                return;
147            }
148            if (distance[new_state]==-1){//未访问过结点
149                distance[new_state]=distance[cur_state]+1;
150                position[new_state]=i;
151                parentState[new_state]=cur_state;
152                EnQueue(q, new_state);
153            }
154        }
155    }
156}

优化过程：将需要改变的状态存放在一个一维数组当中，这样就减少了每次改变状态时的开销。如下所示：

int state[MAXSIZE]={
0xF888,0xF444,0xF222,0xF111,
0x8F88,0x4F44,0x2F22,0x1F11,
0x88F8,0x44F4,0x22F2,0x11F1,

0x888F,0x444F,0x222F,0x111F};

0xF888转换为二进制是1111 1000 1000 1000，换一种格式：

1111

1000

1000

1000

表示改变坐标（0，0）的状态时第一列和第一行的状态都要改变，这样只要和当前状态XOR一下就可以得到新的状态了。

再次提交了一次任然是TLE。。。看来效果不是很明显。

继续改进，发现队列用的是链表实现，效率没有用数组高，因而将链表用数组全部重写。

再次提交，果然AC了。

Run ID	User	Problem	Result	Memory	Time	Language	Code Length	Submit Time
4856540	zen_chou	2965	Accepted	1220K	219MS	C	2387B	2009-03-26 17:27:36

  1#include <stdio.h>
  2#include <stdlib.h>
  3#include <string.h>
  4#define MAXSTATE 65536
  5#define MAXSIZE 16
  6#define ALLOPEN 0
  7//循环队列结构体
  8typedef struct{
  9    int head, tail;
 10    int node[MAXSTATE];
 11}QUEUE;
 12//队列函数
 13void Init(QUEUE *q)
 14{
 15    q->head=q->tail=0;
 16}
 17int Empty(QUEUE *q)
 18{
 19    if ((q->head-q->tail)==0) return 1;
 20    return 0;
 21}
 22void EnQueue(QUEUE *q ,int d)
 23{
 24    if ((q->tail+1)%MAXSTATE==q->head){
 25        printf("Overflow!\n");
 26        return;
 27    }
 28    q->node[q->tail]=d;
 29    q->tail=(q->tail+1)%MAXSTATE;
 30}
 31int DeQueue(QUEUE *q)
 32{
 33    int d;
 34    if (q->head==q->tail) {
 35        printf("Underflow!\n");
 36        return -1;
 37    }
 38    d=q->node[q->head];
 39    q->head=(q->head+1)%MAXSTATE;
 40    return d;
 41}
 42//全局变量
 43int distance[MAXSTATE];
 44int position[MAXSTATE];
 45int parentState[MAXSTATE];
 46QUEUE queue;
 47int state[MAXSIZE]={
 480xF888,0xF444,0xF222,0xF111,
 490x8F88,0x4F44,0x2F22,0x1F11,
 500x88F8,0x44F4,0x22F2,0x11F1,
 510x888F,0x444F,0x222F,0x111F};
 52
 53
 54int ChangeState(int id, int pos)
 55{
 56    int new_id;
 57    new_id=id^state[pos];
 58    return new_id;
 59}
 60
 61void Output(int stat)
 62{
 63    int cur_state, len=0, i;
 64    int arr_x[MAXSIZE];
 65    int arr_y[MAXSIZE];
 66    cur_state=stat;
 67    printf("%d\n", distance[cur_state]);
 68    while(distance[cur_state]!=0){
 69        arr_x[len]=position[cur_state]/4+1;
 70        arr_y[len++]=position[cur_state]%4+1;
 71        cur_state=parentState[cur_state];
 72    }
 73    for (i=len-1;i>=0;i--){
 74        printf("%d %d\n", arr_x[i], arr_y[i]);
 75    }
 76}
 77
 78void main(int argc, char *argv[])
 79{
 80    char c;
 81    int cur_state=0, new_state;
 82    int i=0;
 83    QUEUE *q;
 84    q=&queue;
 85    //freopen("input.txt", "r", stdin);
 86    
 87    while(scanf("%c", &c)!=EOF){
 88        if(c!='\n'){
 89            cur_state<<=1;
 90            if (c=='+') cur_state+=1;
 91        }
 92    }
 93    memset(distance, -1, MAXSTATE*sizeof(int));
 94    
 95    if(cur_state==ALLOPEN){
 96        printf("0\n");
 97        return;
 98    }
 99    parentState[cur_state]=-1;
100    distance[cur_state]=0;
101    position[cur_state]=-1;
102    EnQueue(q, cur_state);
103    while(!Empty(q)){
104        cur_state=DeQueue(q);
105        for (i=0;i<MAXSIZE;i++){
106            new_state=ChangeState(cur_state, i);
107            if (new_state==ALLOPEN){//成功
108                parentState[new_state]=cur_state;
109                position[new_state]=i;
110                distance[new_state]=distance[cur_state]+1;
111                Output(new_state);
112                return;
113            }
114            if (distance[new_state]==-1){//未访问过结点
115                distance[new_state]=distance[cur_state]+1;
116                position[new_state]=i;
117                parentState[new_state]=cur_state;
118                EnQueue(q, new_state);
119            }
120        }
121    }
122}