UVa1601 Morning after holloween 单向BFS方法

　　紫书上的题，一开始全用stl容器结果tle，于是重写一遍全换成自己手写的容器。另外重写判重和互穿的时候还将n=1,2,3时的情况单独分类。AC代码如下。这道题给的内存还是很充足的。
  1 #include<iostream>
  2 #include<memory.h>
  3 #include<string>
  4 #define INIT(x) memset(x,0,sizeof(x))
  5 using namespace std;
  6 
  7 int w, h, n;
  8 int num[20][20];//每个空格的编号
  9 int conn[200][200];//邻接表
 10 int visited[200][200][200];
 11 char G[20][20];
 12 int goal[3];
 13 int start[3];
 14 int queue[10000000][4],front,rear;
 15 void queIns(int a[3],int step)
 16 {
 17     queue[rear][0] = step;
 18     queue[rear][1] = a[0];
 19     queue[rear][2] = a[1];
 20     queue[rear][3] = a[2];
 21     rear += 1;
 22 }
 23 void quePop(){++front;}
 24 int* getQueFront(){
 25     return queue[front];
 26 }
 27 bool queIsEmpty(){return front == rear;}
 28 
 29 void init()
 30 {
 31     INIT(num);
 32     INIT(conn);
 33     INIT(visited);
 34     INIT(G);
 35     INIT(goal);
 36     INIT(start);
 37     INIT(queue);
 38     front = 0; rear = 0;
 39 }
 40 
 41 bool isOverlap(int a[3])//是否位置重叠
 42 {
 43     if (n == 3)
 44     {
 45         return (a[1] == a[2] || a[1] == a[0] || a[2] == a[0]);
 46     }
 47     else if (n == 2)
 48     {
 49         return (a[1] == a[0]);
 50     }
 51     else if (n == 1)
 52     {
 53         return false;
 54     }
 55 }
 56 
 57 bool isAvalible(int a[3], int b[3])//移动是否可行（防止互穿）
 58 {
 59     if (n == 3)
 60     {
 61         if (a[1] == b[2] && a[2] == b[1])return false;
 62         if (a[1] == b[0] && a[0] == b[1])return false;
 63         if (a[0] == b[2] && a[2] == b[0])return false;
 64         else return true;
 65     }
 66     else if (n == 2)
 67     {
 68         if (a[1] == b[0] && a[0] == b[1])return false;
 69         else return true;
 70     }
 71     else if (n == 1) return true;
 72 }
 73 
 74 bool isEqual(int a[3], int b[3])
 75 {
 76     if (a[0] == b[0] && a[2] == b[2] && a[1] == b[1])return true;
 77     else return false;
 78 }
 79 
 80 int bfs()
 81 {
 82     conn[0][0] = 1;
 83     visited[start[0]][start[1]][start[2]] = true;
 84     queIns(start,0);
 85     int curStatus[3],curStep;
 86     int nextStatus[3];
 87     while (!queIsEmpty())
 88     {
 89         curStep = getQueFront()[0];
 90         curStatus[0] = getQueFront()[1];
 91         curStatus[1] = getQueFront()[2];
 92         curStatus[2] = getQueFront()[3];
 93         //cout << curStatus[0] << " " << curStatus[1] << " " << curStatus[2] << " " << endl;
 94         quePop();
 95         if (isEqual(curStatus, goal)) 
 96             return curStep;
 97         //TODO:处理n！=3时此处的取值。
 98         for (int i = 1; i <= conn[curStatus[0]][0]; ++i)
 99         {
100             nextStatus[0] = conn[curStatus[0]][i];
101             for (int j = 1; j <= conn[curStatus[1]][0]; ++j)
102             {
103                 nextStatus[1] = conn[curStatus[1]][j];
104                 for (int k = 1; k <= conn[curStatus[2]][0]; ++k)
105                 {
106                     nextStatus[2] = conn[curStatus[2]][k];
107                     if (isOverlap(nextStatus))continue;//若点重叠则跳过
108                     if (!isAvalible(nextStatus, curStatus)) continue;//若互穿则跳过
109                     if (visited[nextStatus[0]][nextStatus[1]][nextStatus[2]]) continue;//若已经经过这个状态则跳过
110                     //若状态可行
111                     visited[nextStatus[0]][nextStatus[1]][nextStatus[2]]=true;
112                     queIns(nextStatus, curStep + 1);
113                 }
114             }
115         }
116     }
117     return -1;
118 }
119 
120 int dh[] = {1,-1,0,0,0};
121 int dw[] = {0,0,1,-1,0};
122 
123 int main()
124 {
125     ios::sync_with_stdio(false);
126     cin.tie(0);
127     while (cin >> w >> h >> n&&w != 0)
128     {
129         init();
130         int tnum = 1;
131         for (int i = 1; i <= h; ++i)
132         {
133             string line;
134             while (line == "")getline(cin, line);
135             for (int j = 1; j <= w; ++j)
136             {
137                 G[i][j]=line[j-1];
138                 if (G[i][j] != '#') num[i][j] = tnum++;
139                 if (G[i][j] == 'A')goal[0] = num[i][j];
140                 else if (G[i][j] == 'B')goal[1] = num[i][j];
141                 else if (G[i][j] == 'C')goal[2] = num[i][j];
142                 else if (G[i][j] == 'a')start[0] = num[i][j];
143                 else if (G[i][j] == 'b')start[1] = num[i][j];
144                 else if (G[i][j] == 'c')start[2] = num[i][j];
145             }
146         }
147         for (int i = 1; i <= h; ++i)
148         {
149             for (int j = 1; j <= w; ++j)
150             {
151                 if (G[i][j] == '#')continue;
152                 int tpos = 1, ti, tj;
153                 for (int k = 0; k < 5; ++k)
154                 {
155                     ti = i + dh[k];
156                     tj = j + dw[k];
157                     if (ti > 0 && ti <= h&&tj > 0 && tj <= w&&G[ti][tj] != '#')
158                     {
159                         conn[num[i][j]][0] += 1;
160                         conn[num[i][j]][tpos++] = num[ti][tj];
161                     }
162                 }
163             }
164         }
165         int step = bfs();
166         cout << step << endl;
167     }
168 }
View Code
　　回头有时间还是写一下双向BFS和A*试试吧。