如何使用 bfs 算法找到边界点
How to find boundary point using bfs algorithm
我把二维数组看成一个坐标,求一个值为1的坐标值
到目前为止,这是一个非常简单的BFS问题,但我想做的是看下图。
在找1的过程中或者全部找到之后,我想知道边界周围的坐标值,按箭头的顺序或相反的方向。
我需要添加哪些选项才能获取这些信息?
下面是我现在使用的BFS代码。我可以从 BFS 函数中获取坐标值,如第二张图所示。
class Node
{
public int x;
public int y;
public Node(int x, int y)
{
this.x = x;
this.y = y;
}
};
private int[] dx = new int[8] { -1, 0, 1, 0, 1, -1, -1, 1 };
private int[] dy = new int[8] { 0, -1, 0, 1, 1, -1, 1, -1 };
private Queue<Node> q = new Queue<Node>();
bool[,] visit = new bool[15, 15];
int[,] coordinates = new int[15, 15] { { 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, 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, 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 },
{ 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 1, 1, 1, 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, 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, 0 }};
void BFS(int[,] pixel, int x, int y)
{
q.Enqueue(new Node(x, y));
visit[x, y] = true;
while (q.Count != 0)
{
Node cur = q.Dequeue();
for (int i = 0; i < 8; i++)
{
int r = cur.x + dx[i];
int c = cur.y + dy[i];
if (r >= 0 && c >= 0 && r < 15 && c < 15)
{
if (!visit[r, c] && pixel[r, c] == 1)
{
q.Enqueue(new Node(r, c));
visit[r, c] = true;
}
}
}
}
}
void main()
{
for (int y = 0; y < 15; y++)
{
for (int x = 0; x < 15; x++)
{
if (!visit[x, y] && coordinates[x, y] == 1)
{
BFS(coordinates, x, y);
}
}
}
}
我们不需要 BFS 来查找边界“1
”值。我们可以简单地遍历 2D 网格,然后对于每个“1
”,我们可以只检查它的所有 4 个相邻 (i.e up, down, left, right)
值是否都是“1
”。如果其中至少有一个不是'1
',那么它就是一个边界点。谢谢!
find a coordinate value with a value of 1
从预处理矩阵开始
- 搜索所有 1 个值(这也可以递归完成)
- 如果 1 值没有 0 邻居,则表示它不在边缘 - 将其更改为 0。
预处理后你只剩下边缘 1 值,其他都是 0.
I would like to know the coordinate values surrounding the boundary in
the order of the arrow or the other direction
判断边是否形成闭环,并得到正确顺序的节点
将 BFS 应用于预处理矩阵。
从您选择的节点寻找一条路径,回到同一节点(一个循环)。
我把二维数组看成一个坐标,求一个值为1的坐标值
到目前为止,这是一个非常简单的BFS问题,但我想做的是看下图。
在找1的过程中或者全部找到之后,我想知道边界周围的坐标值,按箭头的顺序或相反的方向。
我需要添加哪些选项才能获取这些信息?
下面是我现在使用的BFS代码。我可以从 BFS 函数中获取坐标值,如第二张图所示。
class Node
{
public int x;
public int y;
public Node(int x, int y)
{
this.x = x;
this.y = y;
}
};
private int[] dx = new int[8] { -1, 0, 1, 0, 1, -1, -1, 1 };
private int[] dy = new int[8] { 0, -1, 0, 1, 1, -1, 1, -1 };
private Queue<Node> q = new Queue<Node>();
bool[,] visit = new bool[15, 15];
int[,] coordinates = new int[15, 15] { { 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, 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, 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 },
{ 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 1, 1, 1, 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, 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, 0 }};
void BFS(int[,] pixel, int x, int y)
{
q.Enqueue(new Node(x, y));
visit[x, y] = true;
while (q.Count != 0)
{
Node cur = q.Dequeue();
for (int i = 0; i < 8; i++)
{
int r = cur.x + dx[i];
int c = cur.y + dy[i];
if (r >= 0 && c >= 0 && r < 15 && c < 15)
{
if (!visit[r, c] && pixel[r, c] == 1)
{
q.Enqueue(new Node(r, c));
visit[r, c] = true;
}
}
}
}
}
void main()
{
for (int y = 0; y < 15; y++)
{
for (int x = 0; x < 15; x++)
{
if (!visit[x, y] && coordinates[x, y] == 1)
{
BFS(coordinates, x, y);
}
}
}
}
我们不需要 BFS 来查找边界“1
”值。我们可以简单地遍历 2D 网格,然后对于每个“1
”,我们可以只检查它的所有 4 个相邻 (i.e up, down, left, right)
值是否都是“1
”。如果其中至少有一个不是'1
',那么它就是一个边界点。谢谢!
find a coordinate value with a value of 1
从预处理矩阵开始
- 搜索所有 1 个值(这也可以递归完成)
- 如果 1 值没有 0 邻居,则表示它不在边缘 - 将其更改为 0。
预处理后你只剩下边缘 1 值,其他都是 0.
I would like to know the coordinate values surrounding the boundary in the order of the arrow or the other direction
判断边是否形成闭环,并得到正确顺序的节点
将 BFS 应用于预处理矩阵。
从您选择的节点寻找一条路径,回到同一节点(一个循环)。