[算法]怎么输出迷宫图案,怎么走出迷宫?(以往的帖子看过,但要求不足或没有结果,小弟我有更详细的要求)
[算法]如何输出迷宫图案,如何走出迷宫?(以往的帖子看过,但要求不足或没有结果,我有更详细的要求)
[算法]如何输出迷宫图案,如何走出迷宫?
开篇:
反正无聊,突然想起这两个命题,思考了很久总有无法解决的地方。也看过以往的帖子,感觉回帖思考得不够深如“递归就行”、“遍历就行”等等——请注意我这里有两个特别的要求(祥见下),或者就是“图的DFS遍历”这种我还需要继续学习的东西。
****高手如云,希望大家来讨论讨论如下两个命题的算法:
命题一:如何输出迷宫图案?
程序输入:迷宫矩阵尺寸 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个以上不相邻的边界节点通道树的数量就是通路数量。
以上为判断
生成算法正在想,如果仅有判断算法,然后用穷举法,代价可能很高
------解决方案--------------------
这个算法一定可以保证没有孤岛,没有宽敞的大路,也没有厚实的墙的
[算法]如何输出迷宫图案,如何走出迷宫?
开篇:
反正无聊,突然想起这两个命题,思考了很久总有无法解决的地方。也看过以往的帖子,感觉回帖思考得不够深如“递归就行”、“遍历就行”等等——请注意我这里有两个特别的要求(祥见下),或者就是“图的DFS遍历”这种我还需要继续学习的东西。
****高手如云,希望大家来讨论讨论如下两个命题的算法:
命题一:如何输出迷宫图案?
程序输入:迷宫矩阵尺寸 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; } } }