简单的华容道算法c++实现

#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) { int i; cout << "选择开局布局1~5："; cin >> i; switch (i){ case 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步 case 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步 case 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步 case 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步 case 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步 case 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; //最优解81步，算法未优化，运行时间较长,直接运行系统直接报错 /**************************************************/ } root.father = NULL; root.next = NULL; } bool check_repeat(State *p) { State *traverse; traverse = (State *)head; int record = 0, sum = 0;//record记录对比，sum对比总次数 while (traverse->next) { int remark = record;//跳出双循环 for (int i = 0; i < 5; i++) { for (int j = 0; j < 4; j++) { if (p->state[i][j] != traverse->state[i][j])//状态矩阵出现同位置不同元素，认为是2中不同状态 { record = record + 1; break; }//检查到是一个新状态，记录一次重复 } if (remark != record)break; } //循环对比后，发现是旧状态 traverse = traverse->next; sum = sum + 1; } //遍历结束,对比sum和record，若sum==record 代表每次对比都出现不同状态，说明是一种新状态 if (sum == record)return false; else 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 << "曹操逃出成功！" << endl; show_state( p ); cout << "走法：" << endl; return true; } else return false; } int move(int a[][4],int i,int j,int x,int y,State * &current,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 = show_way.top(); while (show_way.empty() == false) { 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 * &current, 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 = show_way.top(); while (show_way.empty() == false) { cout << "第" << x << "步：" << endl; show_state(show); show_way.pop(); if(show_way.size() != 0)show = show_way.top(); 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 } else 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 } else return false;//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 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 } else return false;//move faild } bool is_four(int p[][4], int i, int j, State * &c, State * &n) { if (p[i][j] == p[i + 1][j] &&