河北网站建设与管理,钢筋网片验收规范及标准,如何做到精准客户推广,安徽六安什么时候解封迷宫老鼠
问题描述
迷宫#xff08;如图 8-9 所示#xff09;是一个矩形区域#xff0c;有一个入口和一个出口。迷宫内部包含不能穿越的墙壁或障碍物。这些障碍物沿着行和列放置#xff0c;与迷宫的边界平行。迷宫的入口在左上角#xff0c;出口在右下角。 假定用 nxm 的…迷宫老鼠
问题描述
迷宫如图 8-9 所示是一个矩形区域有一个入口和一个出口。迷宫内部包含不能穿越的墙壁或障碍物。这些障碍物沿着行和列放置与迷宫的边界平行。迷宫的入口在左上角出口在右下角。 假定用 nxm 的矩阵来描述迷宫矩阵的位置11表示入口nm表示出口n 和m分别代表迷宫的行数和列数。迷宫的每个位置都可用其行号和列号表示。在矩阵中当且仅当在位置ij处有一个障碍时其值为 1否则其值为 0。图 8-10 给出了图8-9 中的迷宫所对应的矩阵表示。迷宫老鼠rat in a maze问题是要寻找一条从入口到出口的路径。路径是一个由位置组成的序列每一个位置都没有障碍而且除入口之外路径上的每个位置都是前一个位置在东、南、西或北方向上相邻的一个位置如图8-11 所示。 我们要编写程序来解决迷宫老鼠问题。假设迷宫是一个方阵即mn且足够小能够整个存储在目标计算机的内存中。程序应是独立的一个用户可以输入自己选择的迷宫来直接寻找迷宫路径。
求解策略
逻辑首先把迷宫的入口作为当前位置。如果当前位置是迷宫出口那么已经找到了一条路径寻找工作结束。如果当前位置不是迷宫出口则在当前位置上放置障碍物以阻止寻找过程又绕回到这个位置。然后检查相邻位置是否有空闲即没有障碍物如果有就移动到一个空闲的相邻位置上然后从这个位置开始寻找通往出口的路径。如果不成功就选择另一个空闲的相邻位置并从它开始寻找通往出口的路径。为了方便移动在进入新的相邻位置之前把当前位置保存在一个栈中。如果所有空闲的相邻位置都已经被探索过但还未能找到路径则表明迷宫不存在从入口到出口的路径。
路径的表示注意在栈中始终有一条从入口到当前位置的路径。如果最终到达了出口那么栈中的路径就是从入口到出口的路径。
padding为了避免在处理内部位置和边界位置时存在差别可以在迷宫的周围增加一圈障碍物。对于一个mxm的数组maze这一圈障碍物将占据数组maze的第0行、第m1行、第0列和第m1列。
最长路径一个没有障碍物的 m× m 迷宫最长的路径可包含 m 2 m^2 m2个位置。
因为路径包含的位置没均不相同而且迷宫仅有 m 2 m^2 m2 个位置所以一条路径所包含的位置最多不超过 m 2 m^2 m2。又因为路径的最后一个位置不必存储到栈中所以在栈中存储的位置最多是 m 2 − 1 m^2 - 1 m2−1。注意在一个没有障碍物的迷宫中在入口和出口之间总有一条最多包含 2m 个位置的路径。
偏移量表例如如果当前位置是34则其右边相邻位置的行坐标为3offset[0].row3列坐标为 4offset[0].col5。 防止走回去为了不重蹈已经走过的位置我们在每一个走过的位置maze[i] [j]上设置障碍物。
代码
#include iostream
#include stack
using namespace std;/*用于存储迷宫地址的结构体*/
struct position
{int row, //行col; //列operator int() const { return row; }friend ostream operator(ostream out, const position x){out ( x.row , x.col );return out;}
};/*创建二维数组*/
template class T
bool make2dArray(T** x, int numberOfRows, int numberOfColumns)
{try {//行指针x new T * [numberOfRows];//为每一行分配内存for (int i 0; i numberOfRows; i)x[i] new int[numberOfColumns];return true;}catch (bad_alloc) { return false; }
}/*遍历二维数组*/
templateclass T
void traverse2dArray(T** x, int numberOfRows, int numberOfColumns)
{for (int i 0; i numberOfRows; i){for (int j 0; j numberOfColumns; j){cout.width(4);cout x[i][j] ;}cout endl;}
}/*迷宫老鼠全局变量*/
int** maze,mazeSize;
stackposition path;//存储路径的数组栈
/*迷宫老鼠问题*/
/*展示界面*/
void welcome()
{cout ******Welcome To RAT IN A MAZE****** endl;cout ************Jasmine,2022************ endl;
}
/*输入迷宫*/
void inputMaze()
{cout Please enter the size of Maze-Matrix:;while (!(cin mazeSize)){cin.clear();//清空标志位while (cin.get() ! \n)//删除无效的输入continue;cout Please enter the size of Maze-Matrix:;}//2的原因是为了避免在处理内部位置和边界位置时存在差别make2dArrayint(maze, mazeSize 2, mazeSize 2);//初始化边界位置的数值for (int i 0; i mazeSize 1; i){maze[i][0] 1;maze[0][i] 1;maze[i][mazeSize 1] 1;maze[mazeSize 1][i] 1;}//初始化迷宫for (int i 1; i mazeSize; i)for(int j 1; j mazeSize; j){int positionij;cout Please enter maze[ i , j ]:;while (!(cin positionij)){cin.clear();//清空标志位while (cin.get() ! \n)//删除无效的输入continue;cout Please enter maze[ i , j ]:;}maze[i][j] positionij;}cout The maze endl;traverse2dArrayint(maze, mazeSize 2, mazeSize 2);
}
/*寻找迷宫路径入口(1,1),出口(size,size)如找到返回true如没找到则返回false*/
bool findPath()
{path stackposition();//存储路径//初始化偏移量position offset[4];offset[0].row 0; offset[0].col 1;//右offset[1].row 1; offset[1].col 0;//下offset[2].row 0; offset[2].col -1;//左offset[3].row -1; offset[3].col 0;//上//入口position here;here.row 1;here.col 1;maze[1][1] 1;//防止回到入口int option 0;//下一步int lastOption 3;//寻找一条路径while ((here.row ! mazeSize) || (here.col ! mazeSize)){int r, c;while (option lastOption){r here.row offset[option].row;c here.col offset[option].col;if (maze[r][c] 0) break;option;//下一个选择}// 相邻的下一步是否找到if (option lastOption){//移到maze[r][c]path.push(here);here.row r;here.col c;maze[r][c] 1;//防止重复访问该节点option 0;}else//如果没找到{if (path.empty())return false;position next path.top();path.pop();if (here.row next.row) // 说明是移动的左右option 2 next.col - here.col; // 如果是左的话op 3就是上如果是右的话op 1就是下else // 此时移动的是上下option 3 next.row - here.row; // 如果是上的话op 4如果是下的话op 2就是左here next;}}path.push(here);return true;
}
/*输出迷宫路径*/
void outputPath()
{int i 0;cout The path ;stackposition temp;while(!path.empty()){cout path.top() -;temp.push(path.top());path.pop();}while(!temp.empty() temp.size() 1){cout temp.top() -;temp.pop();}cout temp.top() endl;temp.pop();
}int main()
{cout RAT IN A MAZE******************** endl;welcome();inputMaze();findPath();outputPath();return 0;
}运行结果
C:\Users\15495\Documents\Jasmine\Work\coding\cmake-build-debug\coding.exe
RAT IN A MAZE********************
******Welcome To RAT IN A MAZE******
************Jasmine,2022************
Please enter the size of Maze-Matrix:3
Please enter maze[1,1]:0
Please enter maze[1,2]:0
Please enter maze[1,3]:0
Please enter maze[2,1]:1
Please enter maze[2,2]:1
Please enter maze[2,3]:0
Please enter maze[3,1]:1
Please enter maze[3,2]:1
Please enter maze[3,3]:0
The maze 1 1 1 1 11 0 0 0 11 1 1 0 11 1 1 0 11 1 1 1 1
The path (3,3)-(2,3)-(1,3)-(1,2)-(1,1)-(1,1)-(1,2)-(1,3)-(2,3)-(3,3)Process finished with exit code 0
