华容道穷举算法实现
1、⼴度优先的树型结构
由于整个棋局的可⾏解可以描述成⼀个树型结构，并且为了得到最少移动步数需要采⽤⼴度优先的搜索算法，因此考虑将链表与树型结构整合起来，便于进⾏⼴度搜索。如图，当我们试图搜索第三步可⾏解时，只需要顺着第⼆步的链表依次搜索便可以实现了。
2、堆栈结构输出最少步数
由于在树型结构设计上，每个⼦节点都保留了⼀个对⽗节点的引⽤。所以⼀旦找到最优解，我们就需要从最底层向上追溯所有移动步骤（如下图）。但这个顺序与⾛棋的顺序正好相反。借助⼀个堆栈结构实现后进先出便把这个次序逆转过来了。
本次算法实现的算法采⽤的是穷举，实现机制就是如上图所⽰，代码⽐较简单，直接上代码:
#include<iostream>
using namespace std;
#include<stack>
struct State
{
State *father;
int state[5][4];
State *next;
};
State *current;
const State *head = current;
State *next_node;
void show_state(State *c)
{
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 4; j++)
{
cout << c->state[i][j] << " | ";
}
cout << endl;
}
}
void input_initial_state(int p[][4], State &root)
void input_initial_state(int p[][4], State &root) {街舞舞种有哪些
int i;
cout << "lect num :";
cin >> i;
switch (i){
ca 1:
p[0][0] = 2; p[0][1] = 6; p[0][2] = 6; p[0][3] = 7; p[1][0] = 2; p[1][1] = 1; p[1][2] = 1; p[1][3] = 3; p[2][0] = 4; p[2][1] = 1; p[2][2] = 1; p[2][3] = 3; p[3][0] = 4; p[3][1] = 7; p[3][2] = 5; p[3][3] = 7; p[4][0] = 0; p[4][1] = 7; p[4][2] = 5; p[4][3] = 0; break;//最优解16步
ca 2:
p[0][0] = 7; p[0][1] = 6; p[0][2] = 6; p[0][3] = 7; p[1][0] = 2; p[1][1] = 1; p[1][2] = 1; p[1][3] = 3; p[2][0] = 2; p[2][1] = 1; p[2][2] = 1; p[2][3] = 3; p[3][0] = 4; p[3][1] = 7; p[3][2] = 7; p[3][3] = 5; p[4][0] = 4; p[4][1] = 0; p[4][2] = 0; p[4][3] = 5; break;//最优解13步
ca 3:
p[0][0] = 2; p[0][1] = 3; p[0][2] = 7; p[0][3] = 7; p[1][0] = 2; p[1][1] = 3; p[1][2] = 7; p[1][3] = 7; p[2][0] = 4; p[2][1] = 5; p[2][2] = 6; p[2][3] = 6; p[3][0] = 4; p[3][1] = 5; p[3][2] = 1; p[3][3] = 1; p[4][0] = 0; p[4][1] = 0; p[4][2] = 1; p[4][3] = 1; break;//最优解22步
ca 4:
p[0][0] = 1; p[0][1] = 1; p[0][2] = 6; p[0][3] = 6; p[1][0] = 1; p[1][1] = 1; p[1][2] = 7; p[1][3] = 7; p[2][0] = 0; p[2][1] = 7; p[2][2] = 7; p[2][3] = 0; p[3][0] = 2; p[3][1] = 3; p[3][2] = 4; p[3][3] = 5; p[4][0] = 2; p[4][1] = 3; p[4][2] = 4; p[4][3] = 5; break;//最优解25步基础解系的个数
ca 5:
p[0][0] = 2; p[0][1] = 7; p[0][2] = 3; p[0][3] = 0; p[1][0] = 2; p[1][1] = 7; p[1][2] = 3; p[1][3] = 7; p[2][0] = 1; p[2][1] = 1; p[2][2] = 4; p[2][3] = 5; p[3][0] = 1; p[3][1] = 1; p[3][2] = 4; p[3][3] = 5; p[4][0] = 6; p[4][1] = 6; p[4][2] = 7; p[4][3] = 0; break;//最优解31步
ca 80:
p[0][0] = 2; p[0][1] = 6; p[0][2] = 6; p[0][3] = 3; p[1][0] = 2; p[1][1] = 7; p[1][2] = 7; p[1][3] = 3; p[2][0] = 4; p[2][1] = 1; p[2][2] = 1; p[2][3] = 5; p[3][0] = 4; p[3][1] = 1; p[3][2] = 1; p[3][3] = 5; p[4][0] = 7; p[4][1] = 0; p[4][2] = 0; p[4][3] = 7; break;
ca 81:
/****************横⼑⽴马**************************/ p[0][0] = 2; p[0][1] = 1; p[0][2] = 1; p[0][3] = 3; p[1][0] = 2; p[1][1] = 1; p[1][2] = 1; p[1][3] = 3; p[2][0] = 4; p[2][1] = 6; p[2][2] = 6; p[2][3] = 5; p[3][0] = 4;
p[3][1] = 7; p[3][2] = 7; p[3][3] = 5; p[4][0] = 7; p[4][1] = 0; p[4][2] = 0; p[4][3] = 7; break;
/**************************************************/
}
root.father = NULL;
< = NULL;
}
bool check_repeat(State *p)
{
State *traver;
traver = (State *)head;
int record = 0, sum = 0;//record记录对⽐，sum对⽐总次数
while (traver->next)
{
int remark = record;//跳出双循环
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 4; j++)
{
if (p->state[i][j] != traver->state[i][j])//状态矩阵出现同位置不同元素，认为是2中不同状态
{
record = record + 1;
break;
}//检查到是⼀个新状态，记录⼀次重复
}
if (remark != record)break;
}
//循环对⽐后，发现是旧状态
traver = traver->next;
sum = sum + 1;
}
//遍历结束，对⽐sum和record，若sum==record 代表每次对⽐都出现不同状态，说明是⼀种新状态
if (sum == record)return fal;
el return true;
}
bool is_success(State *p)
{
if (p->state[3][1] == 1 && p->state[3][2] == 1 && p->state[4][1] == 1 && p->state[4][2] == 1)
乾坤一掷{
工作英语单词cout << "find vale is ok!" << endl;
return true;
}
el return fal;
}
int move(int a[][4],int i,int j,int x,int y,State * ¤t,State * &next_node)//待移动⽬标a[i][j]，移动到位置a[x][y] {
State *p;
next_node->next = new State;
p = next_node->next;
p->next = NULL;
for (int b = 0; b < 5;b++)
{
for (int c = 0; c < 4;c++)
{
p->state[b][c] = a[b][c];
}
}//建⽴新状态结点
int t;
t = p->state[i][j];
p->state[i][j] = p->state[x][y];
恐龙无处不在p->state[x][y] = t;
if (check_repeat(p) == true)
{
delete p;
next_node->next = NULL;
return 1;
};//检查重复
};//检查重复
p->father = current;
//next_node->next = &new_state;
next_node = p;
if (is_success(p))
{
//找到了⽬标状态，输出移动过程
stack <State *> show_way;
while (next_node->father == NULL)
{
show_way.push(next_node);
尿蛋白高怎么办next_node = next_node->father;
}
唯美新娘State *show; int x = 0;
show = p();
while (pty() == fal)
{
cout << "第" << x << "步：" << endl;
show_state(show);
show_way.pop();
x = x + 1;
}
exit(0);
}
return 0;
}
int move(int a[][4], int i1, int j1, int x1, int y1, int i2, int j2, int x2, int y2, State * ¤t, State * &next_node) //待移动⽬标a1[i1][j1]，移动到位置a1[x1][y1]，待移动⽬标a2[i2][j2]，移动到位置a2[x2][y2]
{
State *p;
next_node->next = new State;
p = next_node->next;
p->next = NULL;
for (int b = 0; b < 5; b++)
{
for (int c = 0; c < 4; c++)
{
p->state[b][c] = a[b][c];
}
}//建⽴新状态结点
/* 移动 */
int t;
t = p->state[i1][j1];
p->state[i1][j1] = p->state[x1][y1];
p->state[x1][y1] = t;
t = p->state[i2][j2];
p->state[i2][j2] = p->state[x2][y2];
p->state[x2][y2] = t;
if (check_repeat(p) == true)
{
delete p;
next_node->next = NULL;
return 1;
};//检查重复
p->father = current;
//next_node->next = &new_state;
next_node = p;
if (is_success(p))
{
//找到了⽬标状态，输出移动过程
stack <State *> show_way;
while (next_node->father != NULL)小宇航员
{
show_way.push(next_node);
next_node = next_node->father;
}
State *show; int x = 1;
show = p();
while (pty() == fal)
{
cout << "di" << x << "tps:" << endl;
show_state(show);
show_way.pop();
if(show_way.size() != 0)
show = p();
x = x + 1;
}
exit(0);
}
return 0;
}
bool is_one(int p[][4], int i, int j, State * &c, State * &n)
{
if (p[i][j] == 1 && p[i][j] == p[i + 1][j] && p[i][j] == p[i][j + 1] && p[i][j] == p[i + 1][j + 1])//is 1 or not
{
if (p[i - 1][j] == 0 && p[i - 1][j + 1] == 0 && i > 0){ move(p, i + 1, j, i - 1, j, i + 1, j + 1, i - 1, j + 1, c, n); }//up,2 if (p[i + 2][j] == 0 && p[i + 2][j + 1] == 0 && i < 3){ move(p, i, j, i + 2, j, i, j + 1, i + 2, j + 1, c, n); }//down,2 if (p[i][j - 1] == 0 && p[i + 1][j - 1] == 0 && j > 0){ move(p, i, j + 1, i, j - 1, i + 1, j + 1, i + 1, j - 1, c, n); }//left,2 if (p[i][j + 2] == 0 && p[i + 1][j + 2] == 0 && j < 2){ move(p, i, j, i, j + 2, i + 1, j, i + 1, j + 2, c, n); }//right,2
return true;//move success
}
el return 0;//can not move
}
bool is_two(int p[][4], int i, int j, State * &c, State * &n)
{
if (p[i][j] == p[i + 1][j] && p[i][j] == 2 && p[i + 1][j]==2)//is 2 or not
{
if (p[i - 1][j] == 0 && i > 0){ move(p, i + 1, j, i - 1, j,c,n); }//UP
if (p[i + 2][j] == 0 && i < 3){ move(p, i, j, i + 2, j,c,n); }//DOWN
if (p[i][j - 1] == 0 && p[i + 1][j - 1] == 0 && j > 0){ move(p, i, j, i, j - 1, i + 1, j, i + 1, j - 1, c, n); }//left,2
if (p[i][j + 1] == 0 && p[i + 1][j + 1] == 0 && j < 3){ move(p, i, j, i, j + 1, i + 1, j, i + 1, j + 1, c, n); }//right,2
return true;//move success
}
el return fal;//move faild
}
bool is_three(int p[][4], int i, int j, State * &c, State * &n)
{
if (p[i][j] == p[i + 1][j] && p[i][j] == 3 && p[i + 1][j] == 3)//is 3 or not
{
if (p[i - 1][j] == 0 && i > 0){ move(p, i + 1, j, i - 1, j, c, n); }//UP
if (p[i + 2][j] == 0 && i < 3){ move(p, i, j, i + 2, j, c, n); }//DOWN
