二维数组中的封闭路径

本文关键字：路径 二维数组 | 更新日期: 2023-09-27 18:06:53

存在一个由0和1组成的二维数组。需要一个算法(实现)来确定在这个数组中是否有闭合路径的1，环绕0

例子:

there EXISTS a closed path(center):

1 0 0 0 0
0 0 1 0 0
0 1 0 1 0
0 0 1 1 0
0 0 1 0 0

there is NO

0 0 0 0 1 
0 1 0 1 0
0 0 1 0 0
0 0 1 0 1
0 1 0 1 0

二维数组中的封闭路径

您可以查看Connected Components Labeling算法，例如在Wikipedia或google中查找。例如，这些算法用于在数字黑白图像中分离前景像素和背景像素。为了将它们应用于您的具体问题，您可以将矩阵视为数字图像，其中0表示前景，1表示背景(根据您的需要，反之亦然)。该算法找到被背景(1)包围的最大连接前景区域(仅包含0)。如果你找到这样一个前景区域你就知道它周围有一个1的循环。当前景区域位于边界时，您可以决定是否将其视为包围

这是家庭作业，所以我只给出一个大概的草图。构造一个无向图;每个1是一个节点，相邻的1之间有一条边。谷歌undirected graph cycle detection找到封闭的路径。然后你必须回到原来的矩阵，并确保里面至少有一个0。

另一个想法是从每个0开始，以1 s为界。

这是我尝试的示例代码。测试它我尝试的逻辑是循环遍历除第一行和最后一行以外的所有行。如果你找到0，然后检查它的左，右，上，下邻居，如果所有邻居都是1，然后关闭。

       private void Form1_Load(object sender, EventArgs e)
    {
        int[,] graph = new int[5, 5] { 
        { 1, 0, 0, 0, 0 }, 
        { 0, 0, 1, 0, 0 },
        { 0, 1, 0, 1, 0 }, 
        { 0, 0, 1, 1, 0 }, 
        { 0, 0, 1, 0, 0 } 
        };
        int[,] graph1 = new int[5, 5] { 
        { 0, 0, 0, 0, 1 }, 
        { 0, 1, 0, 1, 0 },
        { 0, 0, 1, 0, 0 }, 
        { 0, 0, 1, 0, 0 }, 
        { 0, 1, 0, 1, 0 } 
        };
        isClosed(graph1);

    }
    private bool isClosed(int[,] graph)
    {

        for (int i = 1; i < graph.GetUpperBound(0); i++)
        {
            for (int j = 1; j < graph.GetUpperBound(1); j++)
            {
                if (graph[i, j] == 0)
                {
                    if (graph[i - 1, j] == 1 && graph[i + 1, j] == 1 && graph[i, j - 1] == 1 && graph[i, j + 1] == 1)
                    {
                        return true;
                    }
                }
            }
        }
        return false;
    }
相关文章：