algorithm - 如何逐层遍历矩阵的元素

Question

很难解释我想要什么。假设我有一个 0 和 1 的矩阵

000000
000000
001100
000000
000000

我想从某一组开始(这个一开始就给定了，然后想往外走。

000000,,,,,,, 000000
011110 或 001100
010010,,,,,,, 010010
011110,,,,,,, 001100
000000,,,,,,, 000000

区别并不重要，只要我会向外经历一切。

我想这样做的原因是，这个 1 和 0 的矩阵对应于某个二维函数的矩阵，我想检查该函数中向外延伸的点。我要

Answer 1

如果我正确理解了这个问题，基本上您想要的是在矩阵中找到一组 1，然后反转这组 1 及其周围的所有元素。这实际上是一个图像处理问题，所以我的解释将是相应的。旁注:术语“多边形”在这里用于矩阵中的 1 组。做了一些假设:多边形总是被填充。多边形不包含任何直接位于矩阵外边界的点(例如:点 (0 , 2) 永远不是多边形的一部分)。可以通过这种方式轻松找到解决方案:

第1步:在矩阵中由1表示的多边形的外边界中搜索任意一个1。通过从左上角开始，可以保证返回的坐标将属于多边形左侧、上侧或角上的 1。

point searchArb1(int[][] matrix)
    list search
    search.add(point(0 , 0))

    while NOT search.isEmpty()
        point pt = search.remove(0)

        //the point wasn't the searched one
        if matrix[pt.x][pt.y] == 1
            return pt

        //continue search in 3 directions: down, right, and diagonally down/right
        point tmp = pt.down()
        if tmp.y < matrix.height
            search.add(tmp)

        tmp = pt.right()
        if tmp.x < matrix.width
            search.add(tmp)

        tmp = pt.diagonal_r_d()
        if tmp.x < matrix.width AND tmp.y < matrix.height
            search.add(tmp)

    return null

第 2 步:既然我们在多边形的外边界中有一个任意点，我们可以简单地通过搜索多边形的外边界来继续。由于上述假设，我们只需要在 3 个方向上搜索 1(对角线总是由 3 个点组成一个角表示)。此方法将顺时针搜索多边形边界。

int UP = 0
int RIGHT = 1
int DOWN = 2
int LEFT = 3

list searchOuterBound(int[][] matrix , point arbp)
    list result

    point pt = arbp
    point ptprev

    //at each point one direction can't be available (determined using the previous found 1
    int dir_unav = LEFT

    do
        result.add(pt)

        //generate all possible candidates for the next point in the polygon bounds
        map candidates

        for int i in [UP , LEFT]
            if i == dir_unav
                continue

            point try
            switch i
                case UP:
                    try = pt.up()
                    break
                case DOWN:
                    try = pt.down()
                    break
                case RIGHT:
                    try = pt.right()
                    break
                case LEFT:
                    try = pt.left()
                    break

            candidates.store(i , try)

        ptprev = pt

        for int i in [0 , 2]
            //the directions can be interpreted as cycle of length 4
            //always start search for the next 1 at the clockwise next direction
            //relatively to the direction we come from
            //eg.: dir_unav = LEFT -> start with UP
            int dir = (dir_unav + i + 1) % 4

            point try = candidates.get(dir)

            if matrix[pt.x][pt.y] == 1
                //found the first match
                pt = try
                //direction we come from is the exact opposite of dir
                dir_unav = (dir + 2) % 4
                break

        //no matching candidate was found
        if pt == ptprev
            return result
    while pt != arbp

    //algorithm has reached the starting point again
    return result

第 3 步:现在我们已经有了多边形的表示。下一步:同时反转多边形周围的点。由于稍后多边形本身会被填充为0，我们可以简单地用1填充多边形中每个点的周围。由于生成这部分矩阵状态有两种选择，我将分为两种解决方案:
步骤3.1:用1s填充与多边形点对角相邻的点

void fillNeighbours_Diagonal_Included(int[][] matrix , list polygon)
    for point p in polygon
        for int x in [-1 , 1]
            for int y in [-1 , 1]
                matrix[p.x + x][p.y + y] = 1

步骤 3.1:不要填充多边形点的对角线相邻点

void fillNeighbours_Diagonal_Excluded(int[][] matrix , list polygon)
    for point p in polygon
        matrix[p.x - 1][p.y] = 1
        matrix[p.x + 1][p.y] = 1
        matrix[p.x][p.y - 1] = 1
        matrix[p.x][p.y + 1] = 1

第 4 步:最后，最后一步:将多边形中的所有 1 反转为 0。注意:我懒得再优化了，所以这部分是暴力实现的。

void invertPolygon(int[][] matrix , list polybounds)
    //go through each line of the matrix
    for int i in [0 , matrix.height]
        sortedlist cut_x

        //search for all intersections of the line with the polygon
        for point p in polybounds
            if p.y == i
                cut_x.add(p.x)

        //remove ranges of points to only keep lines
        int at = 0
        while at < cut_x.size()
            if cut_x.get(at - 1) + 1 == cut_x.get(at) 
               AND cut_x.get(at) == cut_x.get(at + 1) - 1
                   cut_x.remove(at)
                   --at

        //set all points in the line that are part of the polygon to 0
        for int j in [0 , cut_x.size()[ step = 2
            for int x in [cut_x.get(j) , cut_x.get(j + 1)]
                matrix[x][i] = 0

我希望你能理解这背后的基本思想。很抱歉回答很长。