//解华容道的程序，解题时间在100ms以内
//by 半瓶墨水( http://www.2maomao.com/blog/ )
// 相关文章在这里：http://www.2maomao.com/blog/youxi-hrd-online-resolver/
// 可以到这里体验: http://fayaa.com/youxi/hrd/add/
#pragma warning(disable:4530)
#include <stdio.h>
#include <set>
#include <deque>
using namespace std;
typedef __int64 INT64;
typedef unsigned char BYTE;
//!assume int is 32-bit
//block item type
enum BIT {EMPTY=0, DOT, VBAR, HBAR, BOX};
class Board;
//----------------------------------------
//Global variables
set<INT64> g_mbd;
deque<Board*> g_bfs; //Broad-First-Search to ensure shortest path
unsigned int g_index = 0;
//CI is short for Cell Index
#define VALID_CI(x) (x >= 0 && x < 10)
#define IS_BOX(x) (items[x-1]>>5 == BOX)
#define BUILD_BYTE(type, x, y) ((type) << 5 | (x) << 3 | (y))
class Board {
public:
Board(){}
Board(int *layout) {
memset(this, 0, sizeof(*this));
//0xFF mean's boundary
for (int i=0; i<6; i++) {
matrix[0][i] = (BYTE)0xFF;
matrix[6][i] = (BYTE)0xFF;
}
for (int i=0; i<7; i++) {
matrix[i][0] = (BYTE)0xFF;
matrix[i][5] = (BYTE)0xFF;
}
//init the matrix and items
BYTE type = 0;
BYTE x = 0;
BYTE y = 0;
for (int i=0; i<10; i++) {
type = layout[i*3];
x = layout[i*3+1];
y = layout[i*3+2];
items[i] = BUILD_BYTE(type, x, y);
switch (type) {
case DOT: matrix[y+1][x+1] = i+1; break;
case VBAR: matrix[y+1][x+1] = i+1; matrix[y+2][x+1] = i+1; break;
case HBAR: matrix[y+1][x+1] = i+1; matrix[y+1][x+2] = i+1; break;
case BOX: matrix[y+1][x+1] = i+1; matrix[y+1][x+2] = i+1;
matrix[y+2][x+1] = i+1; matrix[y+2][x+2] = i+1; break;
}
}
//find out the empty block
int count = 0;
for (int i=0; i<7; i++)
for (int k=0; k<6; k++)
if (matrix[i][k] == 0)
empty[count++] = k << 4 | i;
}
inline INT64 GetValue() {
INT64 val = 0;
int index = 0;
BYTE bt = 0;
for (int i=1; i<6; i++) {
for (int k=1; k<5; k++) {
index = matrix[i][k] - 1;
bt = VALID_CI(index) ? items[index] >> 5 : 0;
val = val << 3 | bt;
}
}
return val;
}
inline INT64 GetRValue() {
INT64 val = 0;
int index = 0;
BYTE bt = 0;
for (int i=1; i<6; i++) {
for (int k=4; k>0; k--) {
index = matrix[i][k] - 1;
bt = VALID_CI(index) ? items[index] >> 5 : 0;
val = val << 3 | bt;
}
}
return val;
}
void PrintOut() {
printf("\n-----------------------------------\n");
printf("count=%d, parent=%d, empty=(%d,%d),(%d, %d)\n",
g_bfs.size(), parent, empty[0]>>4, empty[0]&0xF, empty[1]>>4, empty[1]&0xF);
printf(" 0 1 2 3 4 5\n");
for (int i=0; i<7; i++) {
printf("%d|", i);
for (int k=0; k<6; k++) {
int index = matrix[i][k] - 1;
if (VALID_CI(index))
printf("%2x", index);
else
printf(" ");
}
printf("\n");
}
}
//spawn new Board by moving the cells around empty cells
// return false if not found
// return true if we got the solution
// the last board in the deque is the solution
bool Spawn() {
//collect the cells around empty cells
BYTE around[8] = {0};
int count = 0;
//DO NOT change the order of ulrd, it's been depended
int ulrd[4][2] = {{0,-1}, {-1,0}, {1,0}, {0,1}};
for (int i=0; i<2; i++) {
int x = empty[i] >> 4;
int y = empty[i] & 0xF;
for (int k=0; k<4; k++) {
int nx = x + ulrd[k][0];
int ny = y + ulrd[k][1];
int index = matrix[ny][nx] - 1;
if (VALID_CI(index)) {
Board *pnewb = new Board();
*pnewb = (*this);
pnewb->level += 1; //it's next level
pnewb->parent = g_index;
if (pnewb->TryAndMove(index, -ulrd[k][0], -ulrd[k][1])) {
INT64 value = 0;
//in Hua-Rong-Dao's rule, move a cell continously
// multi-times, only count as ONE step, so,
// let's give it another chance to move
int moveBack = k ^ 3; //3==0b11, the reverse direction of last move
Board *pnewb2 = new Board();
*pnewb2 = (*pnewb);
//pnewb2->parent = g_bfs.size() - 1;
int d = 0;
for (; d<4; d++) {
if (d == moveBack) continue;
//copy data and add parent
if (pnewb2->TryAndMove(index, -ulrd[d][0], -ulrd[d][1])) {
value = pnewb2->GetValue();
if (g_mbd.find(value) == g_mbd.end()) {
//add new board to bfs and set the board value to map
g_bfs.push_back(pnewb2);
g_mbd.insert(value);
g_mbd.insert(pnewb2->GetRValue());
//Do we win?
if (pnewb2->Win())
return true;
}
break;//ONLY one direction is good due to the rule
}
}
if (d == 4) delete pnewb2;
//-------------------------------------
value = pnewb->GetValue();
if (g_mbd.find(value) == g_mbd.end()) {
//add new board to bfs and set the board value to map
g_bfs.push_back(pnewb);
g_mbd.insert(value);
g_mbd.insert(pnewb->GetRValue());
//Do we win?
if (pnewb->Win())
return true;
continue;
}
}
delete pnewb;
}
}
}
return false;
}
bool Win() {
//return true if the following cell's type is BOX
// 2,4, 3,4, 2,5, 3,5
return IS_BOX(matrix[4][2]) && IS_BOX(matrix[4][3]) &&
IS_BOX(matrix[5][2]);// && IS_BOX(matrix[5][3]);
}
bool TryAndMove(int index, int dx, int dy) {
BYTE item = items[index];
BYTE type = item >> 5;
int x = item >> 3 & 0x03; //0x03==0b11
int y = item & 0x07; //0x07==0b111
bool bRet = false;
//ci is short for cell index
int ci1, ci2, ci3, ci4;
ci1 = ci2 = ci3 = ci4 = 0;
switch (type) {
case DOT:
ci1 = matrix[y+dy+1][x+dx+1];
bRet = !ci1 || ci1==index+1;
if (bRet) {
matrix[y+1][x+1] = 0;
matrix[y+dy+1][x+dx+1] = index + 1;
items[index] = BUILD_BYTE(type, x+dx, y+dy);
SetEmpty(x+1, y+1);
}
break;
case VBAR:
ci1 = matrix[y+dy+1][x+dx+1];
ci2 = matrix[y+dy+2][x+dx+1];
bRet = (!ci1 || ci1==index+1) && (!ci2 || ci2==index+1);
if (bRet) {
matrix[y+1][x+1] = 0;
matrix[y+2][x+1] = 0;
matrix[y+dy+1][x+dx+1] = index + 1;
matrix[y+dy+2][x+dx+1] = index + 1;
items[index] = BUILD_BYTE(type, x+dx, y+dy);
if (matrix[y+1][x+1] == 0) SetEmpty(x+1, y+1);
if (matrix[y+2][x+1] == 0) SetEmpty(x+1, y+2);
}
break;
case HBAR:
ci1 = matrix[y+dy+1][x+dx+1]; ci2 = matrix[y+dy+1][x+dx+2];
bRet = (!ci1 || ci1==index+1) && (!ci2 || ci2==index+1);
if (bRet) {
matrix[y+1][x+1] = 0; matrix[y+1][x+2] = 0;
matrix[y+dy+1][x+dx+1] = index + 1;
matrix[y+dy+1][x+dx+2] = index + 1;
items[index] = BUILD_BYTE(type, x+dx, y+dy);
if (matrix[y+1][x+1] == 0) SetEmpty(x+1, y+1);
if (matrix[y+1][x+2] == 0) SetEmpty(x+2, y+1);
}
break;
case BOX:
ci1 = matrix[y+dy+1][x+dx+1]; ci2 = matrix[y+dy+1][x+dx+2];
ci3 = matrix[y+dy+2][x+dx+1]; ci4 = matrix[y+dy+2][x+dx+2];
bRet = (!ci1 || ci1==index+1) && (!ci2 || ci2==index+1) &&
(!ci3 || ci3==index+1) && (!ci4 || ci4==index+1);
if (bRet) {
matrix[y+1][x+1] = 0; matrix[y+1][x+2] = 0;
matrix[y+2][x+1] = 0; matrix[y+2][x+2] = 0;
matrix[y+dy+1][x+dx+1] = index+1; matrix[y+dy+1][x+dx+2] = index+1;
matrix[y+dy+2][x+dx+1] = index+1; matrix[y+dy+2][x+dx+2] = index+1;
items[index] = BUILD_BYTE(type, x+dx, y+dy);
if (matrix[y+1][x+1] == 0) SetEmpty(x+1, y+1);
if (matrix[y+1][x+2] == 0) SetEmpty(x+2, y+1);
if (matrix[y+2][x+1] == 0) SetEmpty(x+1, y+2);
if (matrix[y+2][x+2] == 0) SetEmpty(x+2, y+2);
}
break;
}
return bRet;
}
void SetEmpty(int ex, int ey) {
int x = empty[0] >> 4;
int y = empty[0] & 0xF;
BYTE *pB = &empty[1];
if (matrix[y][x] != 0)
pB = &empty[0];
(*pB) = (ex<<4) + ey;
}
//Member variables====^_^====^_^====^_^====^_^====^_^====^_^====
int level;
int parent; //parent node position in the deque
BYTE matrix[7][6]; //[1+5+1][1+4+1] of byte, each byte is the (index+1) in items
BYTE empty[2]; //2 empty slot's position in matrix, x = p >> 4, y = p & 0xF
BYTE items[10]; //BIT:3,x:2,y:3), x,y is zero-based
};
//----------------------------------------
//return the board index in g_bfs if succeed
bool SolveTheBoard(const Board &bd) {
Board *pnewb = new Board();
*pnewb = bd;
g_bfs.push_back(pnewb);
g_mbd.insert(pnewb->GetValue());
g_mbd.insert(pnewb->GetRValue());
while (g_index < g_bfs.size()) {
bool bRet = g_bfs[g_index]->Spawn();
if (bRet) return bRet;
g_index++;
}
return false;
}
void PrintSolution() {
deque<Board*> sbs;
Board *pBd = g_bfs[g_bfs.size() - 1];
sbs.push_front(pBd);
printf("Steps = %d\n", pBd->level);
while (pBd->parent != 0) {
pBd = g_bfs[pBd->parent];
sbs.push_front(pBd);
}
for (unsigned int i=0; i<sbs.size(); i++)
sbs[i]->PrintOut();
}
#include<windows.h>
void main() {
//HengDaoLiMa
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 };
//BiYiHengKong
//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 };
Board bd(layout);
DWORD tc1 = GetTickCount();
bool bRet = SolveTheBoard(bd);
DWORD tc2 = GetTickCount();
printf("Total: %d ms\n", tc2-tc1);
if (bRet) {
PrintSolution();
printf(":) bfs=%d, mbd=%d, Solved!\n", g_bfs.size(), g_mbd.size());
} else {
printf(":) bfs=%d, mbd=%d, NO SOLUTION FOUND!\n", g_bfs.size(), g_mbd.size());
}
//delete all items
for (unsigned int i=0; i<g_bfs.size(); i++)
delete g_bfs[i];
}