Как найти граничную точку с помощью алгоритма BFS - PullRequest
Новая
       41

Как найти граничную точку с помощью алгоритма BFS

1 голос
/ 29 марта 2019

Я думаю о 2D-массиве как о координате и пытаюсь найти значение координаты со значением 1.

Пока что это очень простая проблема BFS, но я хочу посмотреть наследующее изображение.

enter image description here

Пока я ищу 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);
            }
        }
    }

}

Ответы [ 2 ]

5 голосов
/ 29 марта 2019

нам не нужна BFS для нахождения граничных значений '1'.Мы можем просто зациклить 2D-сетку, а затем для каждого '1', мы можем просто проверить, являются ли все 4 смежных значения (i.e up, down, left, right) '1' или нет.Если хотя бы один из них не является «1», то это граничная точка.Спасибо!

1 голос
/ 29 марта 2019

найти значение координаты со значением 1

Начните с предварительной обработки матрицы
- Поиск по всем 1 значениям (это также можно сделать рекурсивно)
- Если у значения 1 нет соседа 0, это означает, что оно не на грани - измените его на 0.
После предварительной обработки у вас остаются только значения ребра 1, а все остальные равны 0.

Я хотел бы знать значения координат, окружающие границу в порядок стрелки или другое направление

Чтобы выяснить, образует ли ребро замкнутый цикл, и получить узлы в правильном порядке применить BFS к предварительно обработанной матрице.
Ищите путь от узла по вашему выбору, обратно к тому же узлу (цикл).

...