1

我认为二维数组是一个坐标，并尝试找到一个值为 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);
            }
        }
    }

}
4

2 回答 2

5

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

于 2019-03-29T11:38:26.590 回答
1

找到一个值为 1 的坐标值

从预处理矩阵开始
- 搜索所有 1 值（这也可以递归完成）
- 如果 1 值没有 0 邻居，则意味着它不在边缘 - 将其更改为 0。
预处理后你只剩下边缘 1 的值，其他的都是 0。

我想知道边界周围的坐标值按箭头顺序或其他方向

要确定边是否形成闭环，并以正确的顺序获取节点，请将 BFS 应用于预处理矩阵。
从您选择的节点寻找一条路径，返回同一个节点（循环）。

于 2019-03-29T12:05:23.893 回答