代码
比这篇新的文章:
Gmail 发信
比这篇旧的文章: char_identification.h
作者: 半瓶墨水, 点击2237次, 评论(8), 收藏者(1), , 打分:
所有评论，共8条：( 我也来说两句)
比这篇旧的文章: char_identification.h
华容道最短路径求解程序
语言: C++, 标签: 华容道 求解程序 2008/10/01发布 10个月前更新 更新记录作者: 半瓶墨水, 点击2237次, 评论(8), 收藏者(1), , 打分:
C++语言: 华容道最短路径求解程序
001 //解华容道的程序，解题时间在100ms以内
002 //by 半瓶墨水( http://www.2maomao.com/blog/ )
003 // 相关文章在这里：http://www.2maomao.com/blog/youxi-hrd-online-resolver/
004 // 可以到这里体验: http://fayaa.com/youxi/hrd/add/
005
006 #pragma warning(disable:4530)
007 #include <stdio.h>
008 #include <set>
009 #include <deque>
010 using namespace std;
011 typedef __int64 INT64;
012 typedef unsigned char BYTE;
013 //!assume int is 32-bit
014
015 //block item type
016 enum BIT {EMPTY=0, DOT, VBAR, HBAR, BOX};
017
018 class Board;
019 //----------------------------------------
020 //Global variables
021 set<INT64> g_mbd;
022 deque<Board*> g_bfs; //Broad-First-Search to ensure shortest path
023 unsigned int g_index = 0;
024
025 //CI is short for Cell Index
026 #define VALID_CI(x) (x >= 0 && x < 10)
027 #define IS_BOX(x) (items[x-1]>>5 == BOX)
028 #define BUILD_BYTE(type, x, y) ((type) << 5 | (x) << 3 | (y))
029
030 class Board {
031 public:
032 Board(){}
033 Board(int *layout) {
034 memset(this, 0, sizeof(*this));
035 //0xFF mean's boundary
036 for (int i=0; i<6; i++) {
037 matrix[0][i] = (BYTE)0xFF;
038 matrix[6][i] = (BYTE)0xFF;
039 }
040 for (int i=0; i<7; i++) {
041 matrix[i][0] = (BYTE)0xFF;
042 matrix[i][5] = (BYTE)0xFF;
043 }
044 //init the matrix and items
045 BYTE type = 0;
046 BYTE x = 0;
047 BYTE y = 0;
048 for (int i=0; i<10; i++) {
049 type = layout[i*3];
050 x = layout[i*3+1];
051 y = layout[i*3+2];
052 items[i] = BUILD_BYTE(type, x, y);
053 switch (type) {
054 case DOT: matrix[y+1][x+1] = i+1; break;
055 case VBAR: matrix[y+1][x+1] = i+1; matrix[y+2][x+1] = i+1; break;
056 case HBAR: matrix[y+1][x+1] = i+1; matrix[y+1][x+2] = i+1; break;
057 case BOX: matrix[y+1][x+1] = i+1; matrix[y+1][x+2] = i+1;
058 matrix[y+2][x+1] = i+1; matrix[y+2][x+2] = i+1; break;
059 }
060 }
061 //find out the empty block
062 int count = 0;
063 for (int i=0; i<7; i++)
064 for (int k=0; k<6; k++)
065 if (matrix[i][k] == 0)
066 empty[count++] = k << 4 | i;
067 }
068
069 inline INT64 GetValue() {
070 INT64 val = 0;
071 int index = 0;
072 BYTE bt = 0;
073 for (int i=1; i<6; i++) {
074 for (int k=1; k<5; k++) {
075 index = matrix[i][k] - 1;
076 bt = VALID_CI(index) ? items[index] >> 5 : 0;
077 val = val << 3 | bt;
078 }
079 }
080 return val;
081 }
082 inline INT64 GetRValue() {
083 INT64 val = 0;
084 int index = 0;
085 BYTE bt = 0;
086 for (int i=1; i<6; i++) {
087 for (int k=4; k>0; k--) {
088 index = matrix[i][k] - 1;
089 bt = VALID_CI(index) ? items[index] >> 5 : 0;
090 val = val << 3 | bt;
091 }
092 }
093 return val;
094 }
095 void PrintOut() {
096 printf("\n-----------------------------------\n");
097 printf("count=%d, parent=%d, empty=(%d,%d),(%d, %d)\n",
098 g_bfs.size(), parent, empty[0]>>4, empty[0]&0xF, empty[1]>>4, empty[1]&0xF);
099 printf(" 0 1 2 3 4 5\n");
100 for (int i=0; i<7; i++) {
101 printf("%d|", i);
102 for (int k=0; k<6; k++) {
103 int index = matrix[i][k] - 1;
104 if (VALID_CI(index))
105 printf("%2x", index);
106 else
107 printf(" ");
108 }
109 printf("\n");
110 }
111 }
112 //spawn new Board by moving the cells around empty cells
113 // return false if not found
114 // return true if we got the solution
115 // the last board in the deque is the solution
116 bool Spawn() {
117 //collect the cells around empty cells
118 BYTE around[8] = {0};
119 int count = 0;
120 //DO NOT change the order of ulrd, it's been depended
121 int ulrd[4][2] = {{0,-1}, {-1,0}, {1,0}, {0,1}};
122 for (int i=0; i<2; i++) {
123 int x = empty[i] >> 4;
124 int y = empty[i] & 0xF;
125 for (int k=0; k<4; k++) {
126 int nx = x + ulrd[k][0];
127 int ny = y + ulrd[k][1];
128 int index = matrix[ny][nx] - 1;
129 if (VALID_CI(index)) {
130 Board *pnewb = new Board();
131 *pnewb = (*this);
132 pnewb->level += 1; //it's next level
133 pnewb->parent = g_index;
134 if (pnewb->TryAndMove(index, -ulrd[k][0], -ulrd[k][1])) {
135 INT64 value = 0;
136 //in Hua-Rong-Dao's rule, move a cell continously
137 // multi-times, only count as ONE step, so,
138 // let's give it another chance to move
139 int moveBack = k ^ 3; //3==0b11, the reverse direction of last move
140 Board *pnewb2 = new Board();
141 *pnewb2 = (*pnewb);
142 //pnewb2->parent = g_bfs.size() - 1;
143 int d = 0;
144 for (; d<4; d++) {
145 if (d == moveBack) continue;
146 //copy data and add parent
147 if (pnewb2->TryAndMove(index, -ulrd[d][0], -ulrd[d][1])) {
148 value = pnewb2->GetValue();
149 if (g_mbd.find(value) == g_mbd.end()) {
150 //add new board to bfs and set the board value to map
151 g_bfs.push_back(pnewb2);
152 g_mbd.insert(value);
153 g_mbd.insert(pnewb2->GetRValue());
154 //Do we win?
155 if (pnewb2->Win())
156 return true;
157 }
158 break;//ONLY one direction is good due to the rule
159 }
160 }
161 if (d == 4) delete pnewb2;
162 //-------------------------------------
163
164 value = pnewb->GetValue();
165 if (g_mbd.find(value) == g_mbd.end()) {
166 //add new board to bfs and set the board value to map
167 g_bfs.push_back(pnewb);
168 g_mbd.insert(value);
169 g_mbd.insert(pnewb->GetRValue());
170 //Do we win?
171 if (pnewb->Win())
172 return true;
173
174 continue;
175 }
176 }
177 delete pnewb;
178 }
179 }
180 }
181 return false;
182 }
183
184 bool Win() {
185 //return true if the following cell's type is BOX
186 // 2,4, 3,4, 2,5, 3,5
187 return IS_BOX(matrix[4][2]) && IS_BOX(matrix[4][3]) &&
188 IS_BOX(matrix[5][2]);// && IS_BOX(matrix[5][3]);
189 }
190
191 bool TryAndMove(int index, int dx, int dy) {
192 BYTE item = items[index];
193 BYTE type = item >> 5;
194 int x = item >> 3 & 0x03; //0x03==0b11
195 int y = item & 0x07; //0x07==0b111
196 bool bRet = false;
197 //ci is short for cell index
198 int ci1, ci2, ci3, ci4;
199 ci1 = ci2 = ci3 = ci4 = 0;
200 switch (type) {
201 case DOT:
202 ci1 = matrix[y+dy+1][x+dx+1];
203 bRet = !ci1 || ci1==index+1;
204 if (bRet) {
205 matrix[y+1][x+1] = 0;
206 matrix[y+dy+1][x+dx+1] = index + 1;
207 items[index] = BUILD_BYTE(type, x+dx, y+dy);
208 SetEmpty(x+1, y+1);
209 }
210 break;
211 case VBAR:
212 ci1 = matrix[y+dy+1][x+dx+1];
213 ci2 = matrix[y+dy+2][x+dx+1];
214 bRet = (!ci1 || ci1==index+1) && (!ci2 || ci2==index+1);
215 if (bRet) {
216 matrix[y+1][x+1] = 0;
217 matrix[y+2][x+1] = 0;
218 matrix[y+dy+1][x+dx+1] = index + 1;
219 matrix[y+dy+2][x+dx+1] = index + 1;
220 items[index] = BUILD_BYTE(type, x+dx, y+dy);
221 if (matrix[y+1][x+1] == 0) SetEmpty(x+1, y+1);
222 if (matrix[y+2][x+1] == 0) SetEmpty(x+1, y+2);
223 }
224 break;
225 case HBAR:
226 ci1 = matrix[y+dy+1][x+dx+1]; ci2 = matrix[y+dy+1][x+dx+2];
227 bRet = (!ci1 || ci1==index+1) && (!ci2 || ci2==index+1);
228 if (bRet) {
229 matrix[y+1][x+1] = 0; matrix[y+1][x+2] = 0;
230 matrix[y+dy+1][x+dx+1] = index + 1;
231 matrix[y+dy+1][x+dx+2] = index + 1;
232 items[index] = BUILD_BYTE(type, x+dx, y+dy);
233 if (matrix[y+1][x+1] == 0) SetEmpty(x+1, y+1);
234 if (matrix[y+1][x+2] == 0) SetEmpty(x+2, y+1);
235 }
236 break;
237 case BOX:
238 ci1 = matrix[y+dy+1][x+dx+1]; ci2 = matrix[y+dy+1][x+dx+2];
239 ci3 = matrix[y+dy+2][x+dx+1]; ci4 = matrix[y+dy+2][x+dx+2];
240 bRet = (!ci1 || ci1==index+1) && (!ci2 || ci2==index+1) &&
241 (!ci3 || ci3==index+1) && (!ci4 || ci4==index+1);
242 if (bRet) {
243 matrix[y+1][x+1] = 0; matrix[y+1][x+2] = 0;
244 matrix[y+2][x+1] = 0; matrix[y+2][x+2] = 0;
245 matrix[y+dy+1][x+dx+1] = index+1; matrix[y+dy+1][x+dx+2] = index+1;
246 matrix[y+dy+2][x+dx+1] = index+1; matrix[y+dy+2][x+dx+2] = index+1;
247 items[index] = BUILD_BYTE(type, x+dx, y+dy);
248 if (matrix[y+1][x+1] == 0) SetEmpty(x+1, y+1);
249 if (matrix[y+1][x+2] == 0) SetEmpty(x+2, y+1);
250 if (matrix[y+2][x+1] == 0) SetEmpty(x+1, y+2);
251 if (matrix[y+2][x+2] == 0) SetEmpty(x+2, y+2);
252 }
253 break;
254 }
255 return bRet;
256 }
257
258 void SetEmpty(int ex, int ey) {
259 int x = empty[0] >> 4;
260 int y = empty[0] & 0xF;
261 BYTE *pB = &empty[1];
262 if (matrix[y][x] != 0)
263 pB = &empty[0];
264 (*pB) = (ex<<4) + ey;
265 }
266
267 //Member variables====^_^====^_^====^_^====^_^====^_^====^_^====
268 int level;
269 int parent; //parent node position in the deque
270 BYTE matrix[7][6]; //[1+5+1][1+4+1] of byte, each byte is the (index+1) in items
271 BYTE empty[2]; //2 empty slot's position in matrix, x = p >> 4, y = p & 0xF
272 BYTE items[10]; //BIT:3,x:2,y:3), x,y is zero-based
273 };
274
275 //----------------------------------------
276 //return the board index in g_bfs if succeed
277 bool SolveTheBoard(const Board &bd) {
278 Board *pnewb = new Board();
279 *pnewb = bd;
280 g_bfs.push_back(pnewb);
281 g_mbd.insert(pnewb->GetValue());
282 g_mbd.insert(pnewb->GetRValue());
283 while (g_index < g_bfs.size()) {
284 bool bRet = g_bfs[g_index]->Spawn();
285 if (bRet) return bRet;
286 g_index++;
287 }
288 return false;
289 }
290
291 void PrintSolution() {
292 deque<Board*> sbs;
293 Board *pBd = g_bfs[g_bfs.size() - 1];
294 sbs.push_front(pBd);
295 printf("Steps = %d\n", pBd->level);
296 while (pBd->parent != 0) {
297 pBd = g_bfs[pBd->parent];
298 sbs.push_front(pBd);
299 }
300 for (unsigned int i=0; i<sbs.size(); i++)
301 sbs[i]->PrintOut();
302 }
303
304 #include<windows.h>
305 void main() {
306 //HengDaoLiMa
307 int layout[] = {2,0,0, 4,1,0, 2,3,0, 2,0,2, 3,1,2, 2,3,2, 1,1,3, 1,2,3, 1,0,4, 1,3,4 };
308 //BiYiHengKong
309 //int layout[] = {3,0,0, 4,2,0, 3,0,1, 3,0,2, 3,2,2, 1,0,3, 1,2,3, 2,3,3, 1,0,4, 1,2,4 };
310 Board bd(layout);
311 DWORD tc1 = GetTickCount();
312 bool bRet = SolveTheBoard(bd);
313 DWORD tc2 = GetTickCount();
314 printf("Total: %d ms\n", tc2-tc1);
315 if (bRet) {
316 PrintSolution();
317 printf(":) bfs=%d, mbd=%d, Solved!\n", g_bfs.size(), g_mbd.size());
318 } else {
319 printf(":) bfs=%d, mbd=%d, NO SOLUTION FOUND!\n", g_bfs.size(), g_mbd.size());
320 }
321
322 //delete all items
323 for (unsigned int i=0; i<g_bfs.size(); i++)
324 delete g_bfs[i];
325 }
002 //by 半瓶墨水( http://www.2maomao.com/blog/ )
003 // 相关文章在这里：http://www.2maomao.com/blog/youxi-hrd-online-resolver/
004 // 可以到这里体验: http://fayaa.com/youxi/hrd/add/
005
006 #pragma warning(disable:4530)
007 #include <stdio.h>
008 #include <set>
009 #include <deque>
010 using namespace std;
011 typedef __int64 INT64;
012 typedef unsigned char BYTE;
013 //!assume int is 32-bit
014
015 //block item type
016 enum BIT {EMPTY=0, DOT, VBAR, HBAR, BOX};
017
018 class Board;
019 //----------------------------------------
020 //Global variables
021 set<INT64> g_mbd;
022 deque<Board*> g_bfs; //Broad-First-Search to ensure shortest path
023 unsigned int g_index = 0;
024
025 //CI is short for Cell Index
026 #define VALID_CI(x) (x >= 0 && x < 10)
027 #define IS_BOX(x) (items[x-1]>>5 == BOX)
028 #define BUILD_BYTE(type, x, y) ((type) << 5 | (x) << 3 | (y))
029
030 class Board {
031 public:
032 Board(){}
033 Board(int *layout) {
034 memset(this, 0, sizeof(*this));
035 //0xFF mean's boundary
036 for (int i=0; i<6; i++) {
037 matrix[0][i] = (BYTE)0xFF;
038 matrix[6][i] = (BYTE)0xFF;
039 }
040 for (int i=0; i<7; i++) {
041 matrix[i][0] = (BYTE)0xFF;
042 matrix[i][5] = (BYTE)0xFF;
043 }
044 //init the matrix and items
045 BYTE type = 0;
046 BYTE x = 0;
047 BYTE y = 0;
048 for (int i=0; i<10; i++) {
049 type = layout[i*3];
050 x = layout[i*3+1];
051 y = layout[i*3+2];
052 items[i] = BUILD_BYTE(type, x, y);
053 switch (type) {
054 case DOT: matrix[y+1][x+1] = i+1; break;
055 case VBAR: matrix[y+1][x+1] = i+1; matrix[y+2][x+1] = i+1; break;
056 case HBAR: matrix[y+1][x+1] = i+1; matrix[y+1][x+2] = i+1; break;
057 case BOX: matrix[y+1][x+1] = i+1; matrix[y+1][x+2] = i+1;
058 matrix[y+2][x+1] = i+1; matrix[y+2][x+2] = i+1; break;
059 }
060 }
061 //find out the empty block
062 int count = 0;
063 for (int i=0; i<7; i++)
064 for (int k=0; k<6; k++)
065 if (matrix[i][k] == 0)
066 empty[count++] = k << 4 | i;
067 }
068
069 inline INT64 GetValue() {
070 INT64 val = 0;
071 int index = 0;
072 BYTE bt = 0;
073 for (int i=1; i<6; i++) {
074 for (int k=1; k<5; k++) {
075 index = matrix[i][k] - 1;
076 bt = VALID_CI(index) ? items[index] >> 5 : 0;
077 val = val << 3 | bt;
078 }
079 }
080 return val;
081 }
082 inline INT64 GetRValue() {
083 INT64 val = 0;
084 int index = 0;
085 BYTE bt = 0;
086 for (int i=1; i<6; i++) {
087 for (int k=4; k>0; k--) {
088 index = matrix[i][k] - 1;
089 bt = VALID_CI(index) ? items[index] >> 5 : 0;
090 val = val << 3 | bt;
091 }
092 }
093 return val;
094 }
095 void PrintOut() {
096 printf("\n-----------------------------------\n");
097 printf("count=%d, parent=%d, empty=(%d,%d),(%d, %d)\n",
098 g_bfs.size(), parent, empty[0]>>4, empty[0]&0xF, empty[1]>>4, empty[1]&0xF);
099 printf(" 0 1 2 3 4 5\n");
100 for (int i=0; i<7; i++) {
101 printf("%d|", i);
102 for (int k=0; k<6; k++) {
103 int index = matrix[i][k] - 1;
104 if (VALID_CI(index))
105 printf("%2x", index);
106 else
107 printf(" ");
108 }
109 printf("\n");
110 }
111 }
112 //spawn new Board by moving the cells around empty cells
113 // return false if not found
114 // return true if we got the solution
115 // the last board in the deque is the solution
116 bool Spawn() {
117 //collect the cells around empty cells
118 BYTE around[8] = {0};
119 int count = 0;
120 //DO NOT change the order of ulrd, it's been depended
121 int ulrd[4][2] = {{0,-1}, {-1,0}, {1,0}, {0,1}};
122 for (int i=0; i<2; i++) {
123 int x = empty[i] >> 4;
124 int y = empty[i] & 0xF;
125 for (int k=0; k<4; k++) {
126 int nx = x + ulrd[k][0];
127 int ny = y + ulrd[k][1];
128 int index = matrix[ny][nx] - 1;
129 if (VALID_CI(index)) {
130 Board *pnewb = new Board();
131 *pnewb = (*this);
132 pnewb->level += 1; //it's next level
133 pnewb->parent = g_index;
134 if (pnewb->TryAndMove(index, -ulrd[k][0], -ulrd[k][1])) {
135 INT64 value = 0;
136 //in Hua-Rong-Dao's rule, move a cell continously
137 // multi-times, only count as ONE step, so,
138 // let's give it another chance to move
139 int moveBack = k ^ 3; //3==0b11, the reverse direction of last move
140 Board *pnewb2 = new Board();
141 *pnewb2 = (*pnewb);
142 //pnewb2->parent = g_bfs.size() - 1;
143 int d = 0;
144 for (; d<4; d++) {
145 if (d == moveBack) continue;
146 //copy data and add parent
147 if (pnewb2->TryAndMove(index, -ulrd[d][0], -ulrd[d][1])) {
148 value = pnewb2->GetValue();
149 if (g_mbd.find(value) == g_mbd.end()) {
150 //add new board to bfs and set the board value to map
151 g_bfs.push_back(pnewb2);
152 g_mbd.insert(value);
153 g_mbd.insert(pnewb2->GetRValue());
154 //Do we win?
155 if (pnewb2->Win())
156 return true;
157 }
158 break;//ONLY one direction is good due to the rule
159 }
160 }
161 if (d == 4) delete pnewb2;
162 //-------------------------------------
163
164 value = pnewb->GetValue();
165 if (g_mbd.find(value) == g_mbd.end()) {
166 //add new board to bfs and set the board value to map
167 g_bfs.push_back(pnewb);
168 g_mbd.insert(value);
169 g_mbd.insert(pnewb->GetRValue());
170 //Do we win?
171 if (pnewb->Win())
172 return true;
173
174 continue;
175 }
176 }
177 delete pnewb;
178 }
179 }
180 }
181 return false;
182 }
183
184 bool Win() {
185 //return true if the following cell's type is BOX
186 // 2,4, 3,4, 2,5, 3,5
187 return IS_BOX(matrix[4][2]) && IS_BOX(matrix[4][3]) &&
188 IS_BOX(matrix[5][2]);// && IS_BOX(matrix[5][3]);
189 }
190
191 bool TryAndMove(int index, int dx, int dy) {
192 BYTE item = items[index];
193 BYTE type = item >> 5;
194 int x = item >> 3 & 0x03; //0x03==0b11
195 int y = item & 0x07; //0x07==0b111
196 bool bRet = false;
197 //ci is short for cell index
198 int ci1, ci2, ci3, ci4;
199 ci1 = ci2 = ci3 = ci4 = 0;
200 switch (type) {
201 case DOT:
202 ci1 = matrix[y+dy+1][x+dx+1];
203 bRet = !ci1 || ci1==index+1;
204 if (bRet) {
205 matrix[y+1][x+1] = 0;
206 matrix[y+dy+1][x+dx+1] = index + 1;
207 items[index] = BUILD_BYTE(type, x+dx, y+dy);
208 SetEmpty(x+1, y+1);
209 }
210 break;
211 case VBAR:
212 ci1 = matrix[y+dy+1][x+dx+1];
213 ci2 = matrix[y+dy+2][x+dx+1];
214 bRet = (!ci1 || ci1==index+1) && (!ci2 || ci2==index+1);
215 if (bRet) {
216 matrix[y+1][x+1] = 0;
217 matrix[y+2][x+1] = 0;
218 matrix[y+dy+1][x+dx+1] = index + 1;
219 matrix[y+dy+2][x+dx+1] = index + 1;
220 items[index] = BUILD_BYTE(type, x+dx, y+dy);
221 if (matrix[y+1][x+1] == 0) SetEmpty(x+1, y+1);
222 if (matrix[y+2][x+1] == 0) SetEmpty(x+1, y+2);
223 }
224 break;
225 case HBAR:
226 ci1 = matrix[y+dy+1][x+dx+1]; ci2 = matrix[y+dy+1][x+dx+2];
227 bRet = (!ci1 || ci1==index+1) && (!ci2 || ci2==index+1);
228 if (bRet) {
229 matrix[y+1][x+1] = 0; matrix[y+1][x+2] = 0;
230 matrix[y+dy+1][x+dx+1] = index + 1;
231 matrix[y+dy+1][x+dx+2] = index + 1;
232 items[index] = BUILD_BYTE(type, x+dx, y+dy);
233 if (matrix[y+1][x+1] == 0) SetEmpty(x+1, y+1);
234 if (matrix[y+1][x+2] == 0) SetEmpty(x+2, y+1);
235 }
236 break;
237 case BOX:
238 ci1 = matrix[y+dy+1][x+dx+1]; ci2 = matrix[y+dy+1][x+dx+2];
239 ci3 = matrix[y+dy+2][x+dx+1]; ci4 = matrix[y+dy+2][x+dx+2];
240 bRet = (!ci1 || ci1==index+1) && (!ci2 || ci2==index+1) &&
241 (!ci3 || ci3==index+1) && (!ci4 || ci4==index+1);
242 if (bRet) {
243 matrix[y+1][x+1] = 0; matrix[y+1][x+2] = 0;
244 matrix[y+2][x+1] = 0; matrix[y+2][x+2] = 0;
245 matrix[y+dy+1][x+dx+1] = index+1; matrix[y+dy+1][x+dx+2] = index+1;
246 matrix[y+dy+2][x+dx+1] = index+1; matrix[y+dy+2][x+dx+2] = index+1;
247 items[index] = BUILD_BYTE(type, x+dx, y+dy);
248 if (matrix[y+1][x+1] == 0) SetEmpty(x+1, y+1);
249 if (matrix[y+1][x+2] == 0) SetEmpty(x+2, y+1);
250 if (matrix[y+2][x+1] == 0) SetEmpty(x+1, y+2);
251 if (matrix[y+2][x+2] == 0) SetEmpty(x+2, y+2);
252 }
253 break;
254 }
255 return bRet;
256 }
257
258 void SetEmpty(int ex, int ey) {
259 int x = empty[0] >> 4;
260 int y = empty[0] & 0xF;
261 BYTE *pB = &empty[1];
262 if (matrix[y][x] != 0)
263 pB = &empty[0];
264 (*pB) = (ex<<4) + ey;
265 }
266
267 //Member variables====^_^====^_^====^_^====^_^====^_^====^_^====
268 int level;
269 int parent; //parent node position in the deque
270 BYTE matrix[7][6]; //[1+5+1][1+4+1] of byte, each byte is the (index+1) in items
271 BYTE empty[2]; //2 empty slot's position in matrix, x = p >> 4, y = p & 0xF
272 BYTE items[10]; //BIT:3,x:2,y:3), x,y is zero-based
273 };
274
275 //----------------------------------------
276 //return the board index in g_bfs if succeed
277 bool SolveTheBoard(const Board &bd) {
278 Board *pnewb = new Board();
279 *pnewb = bd;
280 g_bfs.push_back(pnewb);
281 g_mbd.insert(pnewb->GetValue());
282 g_mbd.insert(pnewb->GetRValue());
283 while (g_index < g_bfs.size()) {
284 bool bRet = g_bfs[g_index]->Spawn();
285 if (bRet) return bRet;
286 g_index++;
287 }
288 return false;
289 }
290
291 void PrintSolution() {
292 deque<Board*> sbs;
293 Board *pBd = g_bfs[g_bfs.size() - 1];
294 sbs.push_front(pBd);
295 printf("Steps = %d\n", pBd->level);
296 while (pBd->parent != 0) {
297 pBd = g_bfs[pBd->parent];
298 sbs.push_front(pBd);
299 }
300 for (unsigned int i=0; i<sbs.size(); i++)
301 sbs[i]->PrintOut();
302 }
303
304 #include<windows.h>
305 void main() {
306 //HengDaoLiMa
307 int layout[] = {2,0,0, 4,1,0, 2,3,0, 2,0,2, 3,1,2, 2,3,2, 1,1,3, 1,2,3, 1,0,4, 1,3,4 };
308 //BiYiHengKong
309 //int layout[] = {3,0,0, 4,2,0, 3,0,1, 3,0,2, 3,2,2, 1,0,3, 1,2,3, 2,3,3, 1,0,4, 1,2,4 };
310 Board bd(layout);
311 DWORD tc1 = GetTickCount();
312 bool bRet = SolveTheBoard(bd);
313 DWORD tc2 = GetTickCount();
314 printf("Total: %d ms\n", tc2-tc1);
315 if (bRet) {
316 PrintSolution();
317 printf(":) bfs=%d, mbd=%d, Solved!\n", g_bfs.size(), g_mbd.size());
318 } else {
319 printf(":) bfs=%d, mbd=%d, NO SOLUTION FOUND!\n", g_bfs.size(), g_mbd.size());
320 }
321
322 //delete all items
323 for (unsigned int i=0; i<g_bfs.size(); i++)
324 delete g_bfs[i];
325 }
所有评论，共8条：( 我也来说两句)
| 1 |
3751
1年前
回复
看看http://wmlin.ycool.com/post.2152998.html。最难的华容道题目我的python程序需要5秒。是基于Leo Jay的版本修改的^_^。
|
| 2 |
呵呵，我要做网页上的自动解题程序（近两天上线），所以5秒还是太多了，必须控制在100ms以内。
|
| 3 |
其实我2年前就发现了，华容道的可行局面太少了，完全可以用数据库将解法存起来^_^
|
| 4 |
嗯，时间有限，做东西我都是做到够用就行了
|
| 5 |
华容道自动求解程序的网页版已经做好了，在这里：
|
| 6 |
貌似你的程序不能解第44局？
|
| 7 |
@Leo Jay 呵呵没错，第44局不是标准布局（大于10个方块）
|
| 8 |
@Leo Jay: 已经能解第44局了
|
