《C++穿越迷宫问题》由会员分享，可在线阅读，更多相关《C++穿越迷宫问题（11页珍藏版）》请在金锄头文库上搜索。
1、C+穿越迷宫问题（一直靠着右手边走）穿越迷宫问题（一直靠着右手边走）注：不瞒大伙，这是我这学期学注：不瞒大伙，这是我这学期学 C+期末的时候交的实验期末的时候交的实验报告。报告。由于这是本人自己原创的算法，所以在这里提出，愿与大由于这是本人自己原创的算法，所以在这里提出，愿与大家分享。有不足之处请大伙指出，相互交流讨论。作为初家分享。有不足之处请大伙指出，相互交流讨论。作为初学者，我愿意谨听教诲！学者，我愿意谨听教诲！Duck.2013.6.26一，研究问题一，研究问题 穿越迷宫二，问题阐述二，问题阐述“”表示墙， “ ”表示迷宫中可行路线上的空格，走过的路线用“X”表示。本问 题只研究 12
2、12 规模且只有一个入口和一个出口（迷宫也许会不通）的迷宫。如何从入口 走到出口？三，算法分析三，算法分析问题一，问题一， 迷宫构造迷宫构造 分析分析这个问题是自定义，即我对这个问题制定的规则，没有什么好分析的 解决解决 首先，我用二维字符型数组来表示迷宫的墙和可行路 其次，可由系统产生 0 到 1 的随机数来控制每一个位置产生墙的概率，当然，如果要 使概率可变动，那也无非是传递一个值而已。为使问题简单化，我将产生墙的概率设置为 30%。 第三，将第一行和最后一行全部设置为墙，第一列和最后一列均只有一个可行路。 问题二，问题二， 穿越方式穿越方式 分析分析 这类问题解决的方法应该很多，但就我现
3、在掌握的以及现在的灵感，我只能想到蛮力 的办法。 解决解决 一直沿着穿越者的右手边的墙壁走，如若此迷宫是通的，那一定能找到出口！用递归的办法，我只需要研究当前的位置到下一步的过程就可以了。 问题三，问题三， 方向控制方向控制 分析分析 1、我设置的是二维数组，其动态必须通过数组的下标来控制 2、对于穿越者来说，他的方向只有前后左右，人在其中必定是不知道自己的坐标的 3、有了方向才不能迷失，这对于我们的穿越者也同样如此，每一次作的决策就是选 择方向，即向左转 90还是不转还是向右转 90，这里规定穿越者一次只能选择其中一种， 向左转和向右转的次数从最开始就累计，且一次向左转和一次向右转可抵消为不
4、转 4、由于迷宫是随机构造的，所以也有可能出现类似漩涡一样的路径，所以累计的向 左转或者向右转的次数也有可能超过 3 次，即在空间存在转的角度超过 360，那么就需 要研究同一方向上的转动次数的规律。 解决解决 根据以上分析，需要将做决策时穿越者的状态，具体的说就是穿越者面向的方向，用 坐标绝对位置来表示出来。 规定初始位置人的朝向是坐标方位向右用 sum=0 表示； 每一次穿越者向自己的左边转一次，sum 就减 1； 每一次穿越者向自己的右边转一次，sum 就加 1； 将同一方向上的数字进行研究，可以发现其内在的规律： 绝对向右的数字有-12,-8,-4,0,4,8,12=4n 绝对向上的数
5、字有-13,-9,-5,-1,3,7,11=4n-1 绝对向左的数字有-14,-10,-6,-2,2,6,10=4n-2 据对向下的数字有-11,-7,-3,1,5,9,13=4n+1 由上观察，我发现余数 sum%4 与方向是对应的，就是说余数可以作为方向的判断标 志，根据 C+对%的定义和用法，发现余数与被除数的符号一致，所以这样每个方向上有 两个余数（绝对向右的除外，因为其余数为 0） ，且它们都区别于其他方向上的余数。 这样容易得出 设人的当前坐标为 aij sum%4=0 时，人绝对向右，此时若向前走一步，则为 aij+1 sum%4= 3 or -1 时，人绝对向上，此时若向前走一
6、步，则为 ai-1j sum%4= -3 or 1 时，人绝对向下，此时若向前走一步，则为 ai+1j sum%4= -2 or 2 时，人绝对向左，此时若向前走一步，则为 aij-1 问题四，决策分析问题四，决策分析 过程决策过程决策 分析分析 1 假设前面的路都没有走过 这是核心问题。 这里分析时假定此时人的当前绝对方位是面向右的。 1、 当前穿越者位置特征分析可以肯定，当前位置特征必定是穿越者的右边是一堵墙 2、 穿越者前面环境分析根据排列组合知识可知，有 4（）种情况，即1 21 2CC 1 2 3 4X X X X 人前有路，路右有墙 人前有墙，墙右有墙 人前有墙，墙右有路 人前有路
7、，路右有路 解决解决 1 根据分析，决策可分为三类，即将 2 和 3 合并1 2 3X X X X 针对以上 3 种情况，可有与之相对应的 3 种决策 对于 1，前进一步 对于 2，向左转 对于 3，前进一步，向右转，前进一步 这样，可以看到经过这样的决策，可使得人的右面是墙，便可重复进行上面的决策，递归 便有作用了。整个穿越过程，便是以上过程的循环。 分析分析 2 与解决与解决 2如果前面的路走过，即前方有“X” ，将其与“.”一同看待处理。问题五，决策分析问题五，决策分析 边界决策边界决策 分析分析 根据问题四，可对过程进行决策，但对于递归问题，还有关键的一点就是边界分析决 策。可以注意到
8、，此问题由于是随机产生的迷宫，所以存在不通路的情况，也就是可能会 走回出发点。虽然结果也许我们认为是不同的，但是对于数组来说，都是越界。 解决解决 每一次都对其进行越界判断。如果下一步的坐标经判断是越界的，就不再需要进行问 题四的操作了，就可以直接输出二维数组了，我们的问题也就解决了！四，编程调试四，编程调试第一次编写程序如下： #include #include #include using namespace std ; srand( time(0) ) ; char a1212 ; for ( int k = 0 ; k 11 ) /首先，判断下一步是否出界 for ( int k =
9、0 ; k #include #include using namespace std ; void through( char a1212 , int sum , int i , int j ) if ( ( sum % 4 ) = 0 ) /当前穿越者向右 if ( j + 1 11 ) /首先，判断下一步是否出界 cout “此迷宫可走出！“ endl ; for ( int k = 0 ; k = 11 ; k + ) /如果出界，则输出 for ( int m = 0 ; m = 11 ; m + ) cout akm ; cout endl ; else /如果没有出界，就执行决策
10、 if ( ( ( aij+1 = . ) | ( aij+1 = X ) ) through( a , sum , i , j+1 ) ; if ( aij+1 = ) through( a , sum - 1 , i , j ) ; if ( ( ( aij+1 = . ) |( aij+1 = X) ) ai+1j+1 = X ; through( a , sum + 1 , i + 1 , j + 1 ) ; if ( ( ( sum % 4 ) = 3 ) | ( ( sum % 4 ) = -1 ) ) /当前穿越者向上 if ( ( (ai-1j = .) | (ai-1j =
11、X ) )through( a , sum , i - 1 , j ) ; if ( ai-1j = ) through( a , sum - 1 , i , j ) ; if ( ( ( ai-1j = . ) | ( ai-1j= X ) ) ai-1j+1 = X ; through( a , sum + 1 , i - 1 , j + 1 ) ; if ( ( ( sum % 4 ) = -3) | ( ( sum % 4 ) = 1 ) ) /当前穿越者向下 if ( ( ( ai+1j = . ) | ( ai+1j = X ) ) through( a , sum , i + 1
12、 , j ) ; if ( ai+1j = ) through( a , sum - 1 , i , j ) ; if ( ( ( ai+1j = .) | ( ai+1j = X ) ) ai+1j-1 = X ; through( a , sum + 1 , i + 1 , j - 1 ) ; if ( ( ( sum % 4 ) = 2 ) | ( ( sum % 4 ) = -2 ) ) / 当前穿越者向左 if ( j - 1 0 ) /首先，判断下一步是否出界 cout “此迷宫是死的，走不出“ endl ; for ( int k = 0 ; k = 11 ; k + ) /如果
13、出界，则输出 for ( int m = 0 ; m = 11 ; m + ) cout akm ; cout endl ; else /如果没有出界，就执行决策 if ( ( ( aij-1 = . ) | ( aij-1 = X ) ) through( a , sum , i , j - 1 ) ; if ( aij-1 = ) through( a , sum - 1 , i , j ) ; if ( ( ( aij-1 = . ) | ( aij-1 = X ) ) ai-1j-1 = X ; through( a , sum + 1 , i - 1 , j - 1 ) ; void main() char a1212 ; for ( int k = 0 ; k = 11 ; k + ) /第 1 行和第 12 行为墙 a0k = ; a11k = ; for ( int l = 1 ; l = 10 ; l+ ) /第 1 列和第 12 列为墙 al0 = ; al1
