如何使用 bfs 算法找到边界点

Question

我把二维数组看成一个坐标，求一个值为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);
            }
        }
    }

}

Answer 1

我们不需要 BFS 来查找边界“1”值。我们可以简单地遍历 2D 网格，然后对于每个“1”，我们可以只检查它的所有 4 个相邻 (i.e up, down, left, right) 值是否都是“1”。如果其中至少有一个不是'1'，那么它就是一个边界点。谢谢！

Answer 2

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 应用于预处理矩阵。
从您选择的节点寻找一条路径，回到同一节点（一个循环）。

如何使用 bfs 算法找到边界点

How to find boundary point using bfs algorithm

algorithm

breadth-first-search