[算法]如何输出迷宫图案，如何走出迷宫？(以往的帖子看过，但要求不足或没有结果，我有更详细的要求)
[算法]如何输出迷宫图案，如何走出迷宫？
开篇：
反正无聊，突然想起这两个命题，思考了很久总有无法解决的地方。也看过以往的帖子，感觉回帖思考得不够深如“递归就行”、“遍历就行”等等——请注意我这里有两个特别的要求（祥见下），或者就是“图的DFS遍历”这种我还需要继续学习的东西。
CSDN高手如云，希望大家来讨论讨论如下两个命题的算法：
命题一：如何输出迷宫图案？
程序输入：迷宫矩阵尺寸 m*n，通路条数K。m、n>5;K>=0;
程序输出：一个尺寸为(m+1,n+1)的矩阵。以坐标(0,0)为迷宫起点，坐标(m,n)为迷宫终点。以亮点表示有墙无法通行；以暗点表示无墙阻挡，即通道。示例：
二维矩阵：A = {
0,1,1,1,1,1....
0,0,0,1,0,0....
1,1,0,1,0,1....
1,1,0,0,0,1....
0,1,1,1,1,1....
.....
}
其中的0即表示了迷宫的通路。
要求：
1.孤岛要求：输出的迷宫不存在孤岛。
从通路方面讲，意即不存在无法到达的通路点，如：
{
1,1,1,1,1
1,0,1,0,1
1,0,0,0,1
1,1,1,1,1
}
其中的通路（0的路径）无法到达。注：墙体可以存在孤岛。
2.实心墙要求：输出的迷宫不存在实心墙和宽敞的大通路。
{
0,1,1,1,0
1,1,1,1,0
0,0,1,1,1
0,0,0,0,0
}
其中1的区域有过厚的实心墙。0的区域有过宽的大通路。
3.若K>0，则路径不能交叉。
命题二：如何走出迷宫。
程序输入：满足命题一输出要求的迷宫矩阵。
程序输出：所有能够从起点走到终点的路径。以矩阵下标索引为元素的数组，如输如迷宫：
二维矩阵：A = {
0,1,1,1,1,1....
0,0,0,1,0,0....
1,1,0,1,0,1....
1,1,0,0,0,1....
0,1,1,1,1,1....
.....
}
的输出路径应该为：
LINE = {(0,0),(1,0),(1,1),(1,2),(2,2),(3,2),(3,3),(3,4),(2,4),(1,4),(1,5)...}
注意路径条数K>=0。
两个命题基本上就是这样了，我思前想后只能解决命题二在K=0或K=1时的情况，无法解决K>1的情况。
至于命题一，我实在无力解决孤岛要求和实心墙要求。
[解决办法]
楼主，可能我说的不是很全面，但是可以给你一些帮助。
首先，得知道在真实的情况下如何能走出迷宫，有一个叫做“右手法则”的东西，意思是说但凡这个迷宫有一条能够走出去的路的话，
那么你用右手扶着墙不停的走，肯定能够走出去的，无非是多走一些路而已。
那么实现的时候就简单了，按你说如果0是通路，那么就沿着0去走，碰到1就转完，向着前进方向右侧转，一直走下去就好了，实现起来并不困难。
抛砖引玉而已。有错误，望请指正。
[解决办法]
在效率要求较高而准确性要求接近100%的情况下可以用A星算法.
[解决办法]
LZ是需要自动生成迷宫么?
先把矩阵都用1填满,然后随机选定一个起始点,设为0,然后每次随机选4个方向,按照该方向走,并把到达的点设为0
然后再随机4个方向,以此类推,直到走到另一端!
解迷宫用dfs或bfs都可以!
[解决办法]
判断方法
为图中的墙体和通道建立树形结构
墙体和通道的树形结构建立方法是一样的,下面按照墙体的为例
树形结构建立方法
0、任选一个存在的墙体作为当前根节点
1、遍历节点周围的邻接墙体,作为他的分支,分支最大为8个，如果邻接墙体为他的直接父节点则排除，如果邻接节点为他的兄弟节点，则记录到他自己的属性（A）中，如果邻接节点是树中其他节点则记录在他的属性（B）中
2、遍历节点的子节点重复步骤1直到没有子节点为止。
3、如果图中还存在未归纳到的墙体，则重复0，直到不存在孤立的墙体
判断过宽墙体和过宽通道的方法是一样的，就是如果有节点的属性（A）不为空则说明存在过宽墙体或者过宽通道
判断孤岛，判断墙体树的，如果有一节点的属性B不为空则说明孤岛存在。
通路，判断通道树，如果树形结构中包含2个以上不相邻的边界节点（就是处于图形边缘的通道或者墙体）则说明存在通道，如果这个数量大于2则说明通路存在交叉，在没有交叉的情况下，包含2个以上不相邻的边界节点通道树的数量就是通路数量。
以上为判断
生成算法正在想，如果仅有判断算法，然后用穷举法，代价可能很高
[解决办法]
这个算法一定可以保证没有孤岛，没有宽敞的大路，也没有厚实的墙的
- C# code
using System;using System.Collections.Generic;using System.Text;namespace Maze{ class Maze { public class Path { public Dictionary<int, bool> rooms = new Dictionary<int, bool>(); public Dictionary<Path, bool> neighbors = new Dictionary<Path, bool>(); public Dictionary<int, bool> deletedColumnWalls = new Dictionary<int, bool>(); public Dictionary<int, bool> deletedRowWalls = new Dictionary<int, bool>(); public Path(int id) { rooms.Add(id, true); } public override String ToString() { return rooms.ToString(); } } int row; int column; Random rand = new Random(); List<Path> paths = new List<Path>(); static void Main(string[] args) { Maze m = new Maze(); m.row = 10; m.column = 10; m.run(); m.printResult(); } char EMPTY = ' '; private char[] GRID = { ' ','┃','━','┏', '━','┓','━','┳', '┃','┃','┗','┣', '┛','┫','┻','╋' }; private void printResult() { char[][] grid = new char[row * 2 + 2][];//[column * 2 + 2]; for (int i = 0; i < grid.Length; i++) { grid[i] = new char[column * 2 + 2]; for(int z = 0; z < grid[i].Length; z++) grid[i][z] = EMPTY; } Path path = paths[0]; for(int rowIndex = 0; rowIndex <= row; rowIndex++) { for(int columnIndex = 0; columnIndex <= column; columnIndex++) { int id = columnIndex + rowIndex * column; bool leftWall = rowIndex != row && (columnIndex == 0 || columnIndex == column || !path.deletedColumnWalls.ContainsKey(id - 1)); bool topWall = columnIndex != column && (rowIndex == 0 || rowIndex == row || !path.deletedRowWalls.ContainsKey(id - column)); bool leftTopWall = columnIndex != 0 && (rowIndex == 0 || rowIndex == row || !path.deletedRowWalls.ContainsKey(id - column - 1)); bool topLeftWall = rowIndex != 0 && (columnIndex == 0 || columnIndex == column || !path.deletedColumnWalls.ContainsKey(id - column - 1)); grid[rowIndex * 2 + 1][columnIndex * 2 + 1] = EMPTY; grid[rowIndex * 2 + 1][columnIndex * 2] = leftWall ? '┃' : EMPTY; grid[rowIndex * 2][columnIndex * 2 + 1] = topWall ? '━' : EMPTY; int index = 0; index |= leftWall ? 1 : 0; index |= topWall ? 2 : 0; index |= leftTopWall ? 4 : 0; index |= topLeftWall ? 8 : 0; grid[rowIndex * 2][columnIndex * 2] = GRID[index]; } } grid[1][0] = EMPTY; grid[row * 2 - 1][column * 2] = EMPTY; for (int rowIndex = 0; rowIndex < grid.Length - 1; rowIndex++) { for (int columnIndex = 0; columnIndex < grid[row].Length - 1; columnIndex++) Console.Write(grid[rowIndex][columnIndex]); Console.WriteLine(); } } private void run() { for (int x = 0; x < row; x++) { for (int y = 0; y < column; y++) { int id = x * column + y; Path path = new Path(id); if (y > 0) { Path left = paths[paths.Count - 1]; left.neighbors.Add(path, true); path.neighbors.Add(left, true); } if (x > 0) { Path top = paths[paths.Count - column]; top.neighbors.Add(path, true); path.neighbors.Add(top, true); } paths.Add(path); } } while (paths.Count > 1) mergePaths(); } private void mergePaths() { Path first = paths[rand.Next(paths.Count)]; List<int> options = new List<int>(); for(int i = 0; i < paths.Count; i++) { Path tmp = paths[i]; if(first != tmp) { if(first.neighbors.ContainsKey(tmp)) options.Add(i); } } int secondIndex = options[rand.Next(options.Count)]; Path second = paths[secondIndex]; List<List<int>> connectWalls = getConnectWall(first, second); int wallIndex = rand.Next(connectWalls[0].Count + connectWalls[1].Count); if(wallIndex < connectWalls[0].Count) first.deletedRowWalls.Add(connectWalls[0][wallIndex], true); else first.deletedColumnWalls.Add(connectWalls[1][wallIndex - connectWalls[0].Count], true); first.neighbors.Remove(second); second.neighbors.Remove(first); foreach(Path secondNeighbor in second.neighbors.Keys) { secondNeighbor.neighbors.Remove(second); if(!secondNeighbor.neighbors.ContainsKey(first)) secondNeighbor.neighbors.Add(first, true); if(!first.neighbors.ContainsKey(secondNeighbor)) first.neighbors.Add(secondNeighbor, true); } foreach(int room in second.rooms.Keys) first.rooms.Add(room, true); foreach(int wall in second.deletedRowWalls.Keys) first.deletedRowWalls.Add(wall, true); foreach (int wall in second.deletedColumnWalls.Keys) first.deletedColumnWalls.Add(wall, true); paths.RemoveAt(secondIndex); } private List<List<int>> getConnectWall(Path first, Path second) { List<List<int>> result = new List<List<int>>(); List<int> rowWalls = new List<int>(); List<int> columnWalls = new List<int>(); result.Add(rowWalls); result.Add(columnWalls); bool firstLess = first.rooms.Count <= second.rooms.Count; Dictionary<int, bool> rooms = firstLess ? first.rooms : second.rooms; Dictionary<int, bool> secondRooms = firstLess ? second.rooms : first.rooms; foreach(int room in rooms.Keys) { if(secondRooms.ContainsKey(room - column)) rowWalls.Add(room - column); if (secondRooms.ContainsKey(room + column)) rowWalls.Add(room); int columnIndex = room % column; if (columnIndex > 0 && secondRooms.ContainsKey(room - 1)) columnWalls.Add(room - 1); if (columnIndex < column - 1 && secondRooms.ContainsKey(room + 1)) columnWalls.Add(room); } return result; } }}
[解决办法]
小弟不才，写了一个迷宫生成程序，以抛砖引玉！
- C/C++ code
#include <stdio.h>#include <stdlib.h>struct SPOINT{ int nX; int nY;};struct SMAZEINFO{ char *pWallHor; char *pWallVer; int nWidth; int nHeight; char *pPoints;};void _GenMaze( SMAZEINFO *pMazeInfo, SPOINT *pCurPos ){ // 此函数为递归函数，执行图的深度遍例 const float c_f2PI = 3.1415927f / 2.0f; const int c_nNeiCnt = 4; SPOINT aNeighbors[c_nNeiCnt] = { // 邻点数组，初始值为偏移量 { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } }; int nPtCntX = pMazeInfo->nWidth - 1; int nPtCntY = pMazeInfo->nHeight - 1; int nX = pCurPos->nX; int nY = pCurPos->nY; // 标记当前点已遍例 pMazeInfo->pPoints[ nY * nPtCntX + nX ] = true; if ( nX != nPtCntX - 1 || nY != nPtCntY - 1 ) { // 最后一个点不遍例邻点 for ( int i = 0; i < c_nNeiCnt; ++ i ) { // 循环生成邻点 aNeighbors[i].nX += pCurPos->nX; aNeighbors[i].nY += pCurPos->nY; } for ( int i = 0; i < c_nNeiCnt; ++ i ) { // 乱序邻点，标准shuffle算法 int nRandId = rand() % c_nNeiCnt; if ( nRandId != i ) { SPOINT ptTemp = aNeighbors[i]; aNeighbors[i] = aNeighbors[nRandId]; aNeighbors[nRandId] = ptTemp; } } for ( int i = 0; i < 4; i++ ) { // 遍例相邻点 nX = aNeighbors[i].nX; nY = aNeighbors[i].nY; if ( nX >= 0 && nY >= 0 && nX < nPtCntX && nY < nPtCntY && !pMazeInfo->pPoints[ nY * nPtCntX + nX ] ) { //去除超过边界的点和已遍例的点 if ( nX != pCurPos->nX ) { // 横向通过，打通竖直墙 int nOffset = nX > pCurPos->nX; pMazeInfo->pWallVer[ pCurPos->nY * pMazeInfo->nWidth + pCurPos->nX + nOffset ] = 1; } else { // 纵向通过，打通水平墙 int nOffset = nY > pCurPos->nY; pMazeInfo->pWallHor[ ( pCurPos->nY + nOffset ) * nPtCntX + pCurPos->nX ] = 1; } _GenMaze( pMazeInfo, &aNeighbors[i] ); } } }}void GenMaze( char *pWallHor, char *pWallVer, int nWidth, int nHeight ){ int nPtCntX = nWidth - 1; int nPtCntY = nHeight - 1; char *pPoints = new char[ nPtCntX * nPtCntY ]; memset( pPoints, 0, nPtCntX * nPtCntY ); memset( pWallHor, 0, ( nWidth - 1 ) * nHeight ); memset( pWallVer, 0, nWidth * ( nHeight - 1 ) ); pWallHor[0] = 1; // 打通入口 SMAZEINFO MazeInfo; MazeInfo.pWallVer = pWallVer; MazeInfo.pWallHor = pWallHor; MazeInfo.pPoints = pPoints; MazeInfo.nWidth = nWidth; MazeInfo.nHeight = nHeight; SPOINT ptFirst = { 0 }; _GenMaze( &MazeInfo, &ptFirst ); pWallHor[ nWidth * ( nHeight - 1 ) - 1 ] = 1; // 打通出口}void main(){ srand( (unsigned int)time(0) ); const int nWidth = 15; const int nHeight = 15; char aWallHor[ nWidth * ( nHeight - 1 ) ]; char aWallVer[ ( nWidth - 1 ) * nHeight ]; GenMaze( aWallHor, aWallVer, nWidth, nHeight ); for ( int i = 0; i < nHeight - 1; ++i ) { printf( "@@" ); for ( int j = 0; j < nWidth - 1; ++j ) { printf( aWallHor[ i * ( nWidth - 1 ) + j ] ? " @@" : "@@@@" ); } printf( "\n@@" ); for ( int j = 1; j < nWidth; ++j ) { printf( aWallVer[ i * nWidth + j ] ? " " : " @@" ); } printf( "\n" ); } printf( "@@" ); for ( int j = 0; j < nWidth - 1; ++j ) { printf( aWallHor[ ( nHeight - 1 ) * ( nWidth - 1 ) + j ] ? " @@" : "@@@@" ); } getch(); return;}
[解决办法]
算法简介
把N行M列的迷宫认为是N行M-1列的水平墙和N-1行M列的竖直墙组成的图
N*M的迷宫中一共有(N-1)*(M-1)个通路节点，节点和墙分开存储
每个节点都有上下左右四个方向上的邻点
从入口节点开始执行深度递归遍例，遇到外墙或出口节点则返回
以随机的方式选择邻点，然后再以邻点进行遍例，直到所有节点都被遍例
遍例过程中，每通过一个点就将其标记为已过
向四个方向中的某个方向移动时就把在那个方向上穿过的墙标记为已过
递归过程完成后就得到水平墙和竖直墙的二维数组，1为可过，0为有墙
输出过程不具普适性，不做详解。
@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@ @@ @@ @@ @@ @@
@@@@@@ @@ @@ @@@@@@ @@@@@@@@@@@@@@@@@@ @@@@@@ @@ @@@@@@ @@@@@@ @@ @@
@@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@
@@ @@ @@@@@@@@@@ @@ @@ @@ @@@@@@@@@@@@@@ @@ @@ @@ @@ @@ @@ @@ @@
@@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@
@@ @@@@@@@@@@ @@ @@@@@@ @@@@@@@@@@@@@@ @@ @@ @@ @@@@@@ @@@@@@@@@@ @@
@@ @@ @@ @@ @@ @@ @@ @@ @@ @@
@@ @@@@@@ @@ @@ @@@@@@@@@@@@@@@@@@@@@@ @@@@@@ @@ @@ @@@@@@ @@ @@ @@
@@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@
@@ @@ @@@@@@ @@ @@ @@ @@@@@@@@@@ @@@@@@ @@ @@ @@@@@@@@@@@@@@ @@ @@
@@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@
@@ @@ @@ @@ @@@@@@ @@@@@@ @@ @@@@@@@@@@@@@@@@@@ @@@@@@ @@ @@ @@@@@@
@@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@
@@ @@@@@@ @@ @@ @@@@@@ @@ @@@@@@ @@ @@ @@ @@ @@ @@@@@@ @@@@@@ @@
@@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@
@@@@@@ @@ @@ @@@@@@@@@@@@@@ @@ @@ @@ @@ @@@@@@@@@@@@@@@@@@ @@ @@@@@@
@@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@
@@ @@@@@@@@@@@@@@@@@@@@@@ @@ @@@@@@@@@@@@@@@@@@ @@@@@@ @@ @@@@@@@@@@ @@
@@ @@ @@ @@ @@ @@ @@ @@
@@ @@@@@@ @@@@@@@@@@ @@ @@ @@@@@@ @@@@@@@@@@ @@ @@@@@@@@@@ @@ @@ @@
@@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@
@@ @@ @@@@@@ @@ @@@@@@ @@@@@@@@@@@@@@@@@@@@@@ @@@@@@ @@ @@@@@@ @@ @@
@@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@
@@ @@@@@@ @@ @@@@@@ @@@@@@@@@@ @@ @@@@@@ @@ @@ @@@@@@ @@@@@@ @@@@@@
@@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@
@@ @@ @@@@@@@@@@ @@@@@@@@@@ @@@@@@@@@@ @@@@@@ @@@@@@ @@@@@@ @@ @@ @@
@@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@
@@ @@@@@@ @@ @@@@@@@@@@ @@ @@ @@@@@@@@@@@@@@ @@@@@@ @@ @@@@@@@@@@ @@
@@ @@ @@ @@ @@ @@ @@ @@ @@
@@@@@@@@@@ @@ @@@@@@@@@@@@@@@@@@ @@ @@ @@ @@@@@@ @@@@@@@@@@@@@@@@@@ @@
@@ @@ @@ @@ @@ @@ @@ @@ @@ @@
@@ @@@@@@ @@@@@@@@@@@@@@ @@ @@ @@@@@@ @@@@@@@@@@@@@@ @@@@@@ @@ @@@@@@
@@ @@ @@ @@ @@ @@ @@ @@ @@ @@
@@ @@ @@@@@@ @@@@@@ @@ @@@@@@@@@@ @@@@@@ @@@@@@@@@@ @@ @@@@@@@@@@ @@
@@ @@ @@ @@ @@ @@ @@ @@ @@ @@
@@ @@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@ @@@@@@ @@ @@@@@@@@@@ @@@@@@@@@@
@@ @@ @@ @@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@
[解决办法]
3.4 队列应用举例
例3.5 求迷宫的最短路径：现要求设计一个算法找一条从迷宫入口到出口的最短路径。
本算法要求找一条迷宫的最短路径，算法的基本思想为：从迷宫入口点（1,1）出发，向四周搜索，记下所有一步能到达的坐标点；然后依次再从这些点出发，再记下所有一步能到达的坐标点，…，依此类推，直到到达迷宫的出口点(m,n)为止，然后从出口点沿搜索路径回溯直至入口。这样就找到了一条迷宫的最短路径，否则迷宫无路径。
有关迷宫的数据结构、试探方向、如何防止重复到达某点以避免发生死循环的问题与例3.2处理相同，不同的是：如何存储搜索路径。在搜索过程中必须记下每一个可到达的坐标点，以便从这些点出发继续向四周搜索。由于先到达的点先向下搜索，故引进一个“先进先出”数据结构------队列来保存已到达的坐标点。到达迷宫的出口点(m,n)后，为了能够从出口点沿搜索路径回溯直至入口，对于每一点，记下坐标点的同时，还要记下到达该点的前驱点，因此，用一个结构数组sq[num]作为队列的存储空间，因为迷宫中每个点至多被访问一次，所以num至多等于m*n。sq的每一个结构有三个域：x,y和pre，其中 x,y分别为所到达的点的坐标，pre为前驱点在sq中的坐标，是一个静态链域。除sq外，还有队头、队尾指针：front和rear用来指向队头和队尾元素。
队的定义如下：
- C/C++ code
typedef struct { int x,y; int pre; }sqtype;sqtype sq[num];int front,rear;