如何使用 bfs 查找路径矩阵
本文关键字：路径 查找 何使用 bfs | 更新日期: 2023-09-27 18:31:57
>假设我有一个矩阵，如下所示：
其中 0 表示空格，1 表示第一项，2 项为第二项，3 项为第三项
0 0 0 0 0
0 0 0 0 2
0 0 0 0 0
0 1 0 0 0
0 0 0 0 3
我从(0,0)开始，想参观1,2,3所以就i,j而言，它开始(0,0)->(3,1)->(1,4)->(4,4)
所以为了创造一条我正在思考的道路
- 从起始位置 （0,0） 运行 BFS 到 1 个位置 （3,1）
- 运行 BFS 现在的起始位置将是 （3,1） 到 2 （1,4）
- 运行 BFS 现在的起始位置将是 （1,4） 到 3 （4,4）
要使用BFS，我们需要节点定义及其子节点，但该怎么做呢？到目前为止，我有：
using System;
using System.IO;
using System.Collections.Generic;
using System.Text;
using System.Collections;
namespace ejercicio2
{
class Program
{
struct position
{
public int row;
public int col;
};
const int NOT_VISITED = 0;
static int[,] map = {
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 2},
{0, 0, 0, 0, 0},
{0, 1, 0, 0, 0},
{0, 0, 0, 0, 3}
};
static void Main()
{
int who = 1;
position start;
start.row = 0;
start.col = 0;
//find 1
bfs(start, map, who);
start.row = 3;
start.col = 1;
//find 2
who = 2;
bfs(start, map,who);
start.row = 1;
start.col = 4;
//find 3
who = 3;
bfs(start, map,who);
}
static void bfs(position present, int[,] map, int lookingfor)
{
//how to look for looking for??
}
private bool visited(int[,] board, position cell)
{
return board[cell.row, cell.col] < 1;
}
}
}
using System.IO;
using System;
using System.Collections.Generic;
class Program
{
struct direction
{
public int x;
public int y;
};
static direction[] directions = {
new direction(){x = 1, y = 0},
new direction(){x = 0, y = 1},
new direction(){x = -1, y = 0},
new direction(){x = 0, y = -1}
};
static int[,] visitedmap = resetVisitedMap();
struct position
{
public int row;
public int col;
};
const int NOT_VISITED = 0;
static int[,] map = {
{0, 4, 0, 0, 0},
{0, 0, 0, 0, 2},
{0, 0, 0, 0, 0},
{0, 1, 0, 0, 0},
{0, 0, 0, 0, 3}
};
static void Main()
{
int[] who = new int[]{1,2,3,4};
position start;
start.row = 0;
start.col = 0;
Console.Write("("+start.row+","+start.col+")");
//find 1
foreach(int lookingfor in who){
start = bfs(start, map, lookingfor);
Console.Write("->("+start.row+","+start.col+")");
}
}
static position bfs(position present, int[,] map, int lookingfor)
{
position[] poses = new position[]{present};
bool found = false;
while (!found){
foreach (position pos in poses){
if (map[pos.row, pos.col] == lookingfor){
// Console.Write("------->Success at : ("+pos.row+","+pos.col+")");
visitedmap = resetVisitedMap();
return pos;
}
}
poses = cellsNear(poses);
}
return present;
}
static position[] cellsNear(position pos){
//Console.WriteLine("Looking for cells near (" + pos.row +","+pos.col+")" );
List<position> result = new List<position>();
foreach (direction dir in directions){
int rowCalculated = pos.row + dir.x;
int colCalculated = pos.col + dir.y;
if (rowCalculated >= 0 &&
colCalculated >= 0 &&
rowCalculated < map.GetLength(0) &&
colCalculated < map.GetLength(1) &&
!visited(rowCalculated,colCalculated)){
visitedmap[rowCalculated,colCalculated] = 1;
result.Add(new position(){row =rowCalculated, col = colCalculated });
//Console.WriteLine("found children cell : ("+rowCalculated+","+colCalculated+")" );
}
}
//Console.WriteLine("'n");
return result.ToArray();
}
static position[] cellsNear(position[] poses){
List<position> result = new List<position>();
foreach (position pos in poses){
result.AddRange(cellsNear(pos));
}
return result.ToArray();
}
static bool visited(int row, int col)
{
return visitedmap[row, col] == 1;
}
static int[,] resetVisitedMap(){
return new int[,]{
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0}
};
}
}
只需取消带有日志记录的注释行即可查看搜索的执行方式。如果您有问题，请随时提问。
此处代码具有完整路径
using System.IO;
using System;
using System.Collections.Generic;
class Program
{
struct direction
{
public int x;
public int y;
};
static direction[] directions = {
new direction(){x = 1, y = 0},
new direction(){x = 0, y = 1},
new direction(){x = -1, y = 0},
new direction(){x = 0, y = -1}
};
static int[,] visitedmap = resetVisitedMap();
class Position
{
public int row;
public int col;
public Position parent;
};
const int NOT_VISITED = 0;
static int[,] map = {
{0, 4, 0, 0, 0},
{0, 0, 0, 0, 2},
{0, 0, 0, 0, 0},
{0, 1, 0, 0, 0},
{0, 0, 0, 0, 3}
};
static void Main()
{
int[] who = new int[]{1,2,3,4};
Position start = new Position();
start.row = 0;
start.col = 0;
start.parent = null;
Console.Write("("+start.row+","+start.col+")");
//find 1
foreach(int lookingfor in who){
start = bfs(start, map, lookingfor);
Console.Write("->("+start.row+","+start.col+")");
}
Console.Write("'n Full path :'n");
string path = "";
while (start != null){
path = "->("+ start.row+","+start.col+")"+path;
start = start.parent;
}
Console.Write(path);
}
static Position bfs(Position present, int[,] map, int lookingfor)
{
Position[] poses = new Position[]{present};
bool found = false;
while (!found){
foreach (Position pos in poses){
if (map[pos.row, pos.col] == lookingfor){
// Console.Write("------->Success at : ("+pos.row+","+pos.col+")");
visitedmap = resetVisitedMap();
return pos;
}
}
poses = cellsNear(poses);
}
return present;
}
static Position[] cellsNear(Position pos){
//Console.WriteLine("Looking for cells near (" + pos.row +","+pos.col+")" );
List<Position> result = new List<Position>();
foreach (direction dir in directions){
int rowCalculated = pos.row + dir.x;
int colCalculated = pos.col + dir.y;
if (rowCalculated >= 0 &&
colCalculated >= 0 &&
rowCalculated < map.GetLength(0) &&
colCalculated < map.GetLength(1) &&
!visited(rowCalculated,colCalculated)){
visitedmap[rowCalculated,colCalculated] = 1;
Position posPath = new Position();
posPath.col = colCalculated;
posPath.row = rowCalculated;
posPath.parent = pos;
result.Add(posPath);
//Console.WriteLine("found children cell : ("+rowCalculated+","+colCalculated+")" );
}
}
//Console.WriteLine("'n");
return result.ToArray();
}
static Position[] cellsNear(Position[] poses){
List<Position> result = new List<Position>();
foreach (Position pos in poses){
result.AddRange(cellsNear(pos));
}
return result.ToArray();
}
static bool visited(int row, int col)
{
return visitedmap[row, col] == 1;
}
static int[,] resetVisitedMap(){
return new int[,]{
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0}
};
}
}
如您所见，它不使用集合中的堆栈，而是使用一种内存堆栈，为BFS问题提供了更清晰的解决方案，因为它模拟了一棵树