青蛙换位问题之递归回溯法-

青蛙换位问题之递归回溯法青蛙换位的回溯问题并不是一个很复杂的问题，其中回溯就可以用迭代和递归的方法来实现，本人这里就只用递归回溯法了。本文章主要是参考了huey2672的一篇博客[青蛙换位]，并对将其改为C++版本的。主要的思路呢就是在每进行下一步跳跃的时候就下搜索所有的石块上可以移动的青蛙，并依次移动，每一步中都需要保存当前跳动的青蛙所在的位置到step[n]（n表示当前的步数），这样方便之后的打印青蛙跳动的

青蛙换位的回溯问题并不是一个很复杂的问题，其中回溯就可以用迭代和递归的方法来实现，本人这里就只用递归回溯法了。本文章主要是参考了huey2672的一篇博客[青蛙换位]，并对将其改为C++版本的。
主要的思路呢就是在每进行下一步跳跃的时候就下搜索所有的石块上可以移动的青蛙，并依次移动，每一步中都需要保存当前跳动的青蛙所在的位置到step[n]（n表示当前的步数），这样方便之后的打印青蛙跳动的过程。并且需要保留当前的空位所在的位置，将用来把青蛙放回原处，来实现回溯，具体的实现过程在代码中都有详细的说明。
这里就不多啰嗦了，直接“上菜”。

#include <iostream>#include <fstream>#include <algorithm>using namespace std;#define GREEN 1 //表示公青蛙#define RED 2 //表示母青蛙#define EMPTY 0 //表示空位#define NUM 7 //石头的数目#define MAXSTEP 20 // 完成移位可能需要的步数void recursive_backtrack(int n);//递归回溯法bool can_shift(int i);                  // 判断在第i个石头上青蛙是否能移位void frog_shift(int i);                 // 在第i个石头上青蛙移位int where_empty();                      // 计算空位的位置bool is_success();                      // 判断是否已经完成所有移位void print_result();                    // 打印结果void print_stone();                     //打印石头的状态//stone[i]表示第i+1个石头上的状态是公青蛙、母青蛙还是空static int stone[NUM] = { GREEN, GREEN, GREEN, EMPTY, RED, RED, RED};//记录下每一步中，移动的青蛙所在的石头下标，最终打印过程有用static int step[MAXSTEP] = {-1};int main(){for(size_t i = 0; i < MAXSTEP; i++)step[i] = -1;recursive_backtrack(0);system("pause");return 0;}/* ** 递归回溯法求解 ** n表示递归的深度数，即执行的步骤 */void recursive_backtrack(int n){if(is_success()){print_result();return;}else{int empty_lastpost;//从第1块（对应下标0）石头上开始计算可以移动的frogfor(size_t i = 0; i < NUM; i++){//记录下这步中空位的初始位置，方便回溯empty_lastpost = where_empty();//如果第i+1块石头上的青蛙可以移动if(can_shift(i)){//移动第i+1块石头上的青蛙frog_shift(i);//记录下第n步跳动的青蛙所在石头的下标step[n] = i;//进入下一次的递归recursive_backtrack(n+1);//回溯，将青蛙移回原来的位置 frog_shift(empty_lastpost);}}}}/* ** 判断在第i个石头上青蛙是否能移位 */bool can_shift(int i){int empty_post = where_empty();//记录下空位所在的位置switch(stone[i]){case GREEN:if(empty_post > i && empty_post <= i+2)return true;break;case RED:if(empty_post < i && empty_post >= i-2)return true;break;case EMPTY:default:return false;break;}return false;}/* ** 在第i块石头上的青蛙进行移位 */void frog_shift(int i){swap(stone[where_empty()], stone[i]);}/* ** 计算空位的位置 */int where_empty(){int i;for (i = 0; i < NUM; i++)if (stone[i] == EMPTY) break;return i;}/* ** 判断是否已经完成所有移位 */bool is_success(){if (stone[0] == RED &&stone[1] == RED &&stone[2] == RED &&stone[3] == EMPTY &&stone[4] == GREEN &&stone[5] == GREEN &&stone[6] == GREEN)return true;return false;}/* ** 打印结果 */void print_result(){size_t i;for(i = 0;i < NUM; i++){if(i < 3)stone[i] = GREEN;else if(i > 3)stone[i] = RED;else if(i == 3)stone[i] = EMPTY;}print_stone();for (i = 0; i < MAXSTEP; i++) {if (step[i] == -1)break;swap(stone[where_empty()], stone[step[i]]);print_stone();}cout << endl;}/* ** 打印石头的状态 */void print_stone(){for(size_t i = 0; i < NUM; i++){if(stone[i] == GREEN)cout << "GREEN ";else if(stone)))))))![![tp://bl](https://www.gzzwz.com.cn/uploads/202512/10/7a2764b71d8c1533.webp)](https://img-blog.csdn.net/20161129110325166i] == RED)cout << "RED ";else if(stone[i] == EMPTY)cout << "EMPTY ";}cout << endl;}

是否还在为Ide开发工具频繁失效而烦恼，来吧关注以下公众号获取最新激活方式。亲测可用！

为防止网络爬虫，请关注公众号回复”口令”

激活idea 激活CLion DataGrip DataSpell dotCover dotMemory dotTrace GoLand PhpStorm PyCharm ReSharper ReShaC++ Rider RubyMine WebStorm 全家桶 解锁下载刷新

【正版授权，激活自己账号】：Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛

【官方授权 正版激活】：官方授权 正版激活 自己使用，支持Jetbrains家族下所有IDE…

输出结果如下：
(http://blog.csdn.net/huey2672/article/details/8897770)