V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
iOS 开发实用技术导航
NSHipster 中文版
http://nshipster.cn/
cocos2d 开源 2D 游戏引擎
http://www.cocos2d-iphone.org/
CocoaPods
http://cocoapods.org/
Google Analytics for Mobile 统计解决方案
http://code.google.com/mobile/analytics/
WWDC
https://developer.apple.com/wwdc/
Design Guides and Resources
https://developer.apple.com/design/
Transcripts of WWDC sessions
http://asciiwwdc.com
Cocoa with Love
http://cocoawithlove.com/
Cocoa Dev Central
http://cocoadevcentral.com/
NSHipster
http://nshipster.com/
Style Guides
Google Objective-C Style Guide
NYTimes Objective-C Style Guide
Useful Tools and Services
Charles Web Debugging Proxy
Smore
magic3584
V2EX  ›  iDev

请教一下大佬们二维矩阵的 DFS 问题,不知道为什么总是报错

  •  
  •   magic3584 · 2023-11-14 16:50:46 +08:00 · 1493 次点击
    这是一个创建于 373 天前的主题,其中的信息可能已经有所发展或是发生改变。

    业务场景:

    有个二维矩阵 513 * 513 ,取值只有 0 或 1 ,根据值绘图,0 白色 1 黑色。 现在需要把不规则的黑色绘制成矩形,如下图: Imgur

    代码如下:

    func findConnectedRegion(matrix: [[Int]]) -> [[(Int, Int)]] {
            var result: [[(Int, Int)]] = []
            //    var visited: Set<(Int, Int)> = []
            var visited: Set<String> = []
            let numRows = matrix.count
            let numCols = matrix[0].count
            
            for i in 0..<matrix.count {
                for j in 0..<matrix[0].count {
                    let position = (i, j)
                    let str = String(i)+"-"+String(j)
                    if matrix[i][j] == 1 && !visited.contains(str) {
                        var region: [(Int, Int)] = []
                        dfs(matrix: matrix, rows: numRows,cols: numCols,position: position, visited: visited, region: &region)
                        result.append(region)
                    }
                }
            }
            
            return result
        }
        
        func dfs(matrix: [[Int]],rows:Int,cols:Int,position: (Int, Int), visited: Set<String>, region: inout [(Int, Int)]) {
    //        let numRows = matrix.count
    //        let numCols = matrix[0].count
            
            let numRows = rows
            let numCols = cols
            
            let (row, col) = position
            self.str = String(position.0)+"-"+String(position.1)
            
            // Check if the current position is within bounds and is part of the region
            guard row >= 0, row < numRows, col >= 0, col < numCols, matrix[row][col] == 1, !visited.contains(str) else {
                return
            }
            
            self.visited.insert(str)
            region.append(position)
            
            // Explore neighbors in all four directions
            dfs(matrix: matrix,rows: numRows,cols: numCols, position: (row - 1, col), visited: visited, region: &region)  // Up
            dfs(matrix: matrix, rows: numRows,cols: numCols,position: (row + 1, col), visited: visited, region: &region)  // Down
            dfs(matrix: matrix, rows: numRows,cols: numCols,position: (row, col - 1), visited: visited, region: &region)  // Left
            dfs(matrix: matrix, rows: numRows,cols: numCols,position: (row, col + 1), visited: visited, region: &region)  // Right
        }
    

    好几处局部变量改成了属性,但还是不同位置报相同的错:Thread 1: EXC_BAD_ACCESS (code=2, address=0x16b6a7fc0)

    Imgur

    完全不知道问题出在哪了,请大佬指点

    第 1 条附言  ·  2023-11-15 11:52:34 +08:00
    我把 UP 那一行注释掉以后就好了,不太懂为什么。。。
    第 2 条附言  ·  2023-11-15 15:51:21 +08:00
    已经使用 BFS 解决。
    结果跟 DFS 的差了一点,毕竟 DFS 我注释了一行
    18 条回复    2023-11-15 14:03:33 +08:00
    magic3584
        1
    magic3584  
    OP
       2023-11-14 16:51:58 +08:00
    一楼请喵大 @onevcat
    iOCZS
        2
    iOCZS  
       2023-11-14 18:11:14 +08:00
    要进行图像分割,确定哪一些点是一个整体的,那么获取最小 x ,最大 x 以及最小 y 和最大 y 就能圈定这个矩形了。
    nagisaushio
        3
    nagisaushio  
       2023-11-14 18:16:32 +08:00 via Android
    self.visited.insert?
    magic3584
        4
    magic3584  
    OP
       2023-11-14 18:24:19 +08:00
    @iOCZS #2
    是,现在用的 DFS 去划分多个区域。
    使用 513*513 的随机矩阵没啥问题。实际情况可能是递归太多爆栈了,可能

    所以还可以怎么去确定这个区域呢?
    magic3584
        5
    magic3584  
    OP
       2023-11-14 18:25:19 +08:00
    @nagisaushio #3
    本来用的局部变量,但是一直报错,改成全局了以后,别的地方又报错了[笑哭]
    bing89757
        6
    bing89757  
       2023-11-14 19:24:00 +08:00
    没接触过,不过我感觉找边界就行了吧 找到后再取每个边界的最大最小值 就可以了
    hefish
        7
    hefish  
       2023-11-14 19:27:32 +08:00
    我想应该是 先遍历找起点,找到起点之后,找联通,凡是联通的都记录下来,表示是一个形状里面的,联通找完之后,继续遍历,找下一个起点,直到所有点找完。。
    churchill
        8
    churchill  
       2023-11-14 19:36:18 +08:00
    先找联通区域呀,BFS ,然后每个联通区域算包围盒
    Yuhyeong
        9
    Yuhyeong  
       2023-11-14 19:57:31 +08:00
    @magic3584 在同一个地址出报错,有没有可能是因为之前运行的时候内存没有处理,之前写题,这种情况偶尔会见到。
    czfy
        10
    czfy  
       2023-11-14 20:09:30 +08:00
    试试这样?


    func findConnectedRegions(matrix: [[Int]]) -> [[[(Int, Int)]]] {

    var result: [[[(Int, Int)]]] = []

    for i in 0..<matrix.count {
    for j in 0..<matrix[0].count {

    if matrix[i][j] == 1 {

    var region: [(Int, Int)] = []
    var visited = Set<(Int, Int)>()

    dfs(matrix: matrix, position: (i, j), visited: &visited, region: &region)

    let bound = getRegionBounds(region)
    result.append(bound)

    }

    }
    }

    return result

    }

    func dfs(matrix: [[Int]], position: (Int, Int), visited: inout Set<(Int, Int)>, region: inout [(Int, Int)]) {

    let (row, col) = position

    guard row >= 0, row < matrix.count, col >= 0, col < matrix[0].count, matrix[row][col] == 1, !visited.contains((row, col)) else {
    return
    }

    visited.insert((row, col))
    region.append((row, col))

    dfs(matrix: matrix, position: (row-1, col), visited: &visited, region: &region)
    dfs(matrix: matrix, position: (row+1, col), visited: &visited, region: &region)
    // ...

    }

    func getRegionBounds(_ region: [(Int, Int)]) -> [(Int, Int)] {
    // return bounding box
    }
    magic3584
        11
    magic3584  
    OP
       2023-11-15 09:02:54 +08:00
    @bing89757 #6
    @hefish #7
    @churchill #8
    第一个方法就是先找联通区域。用个简单的矩阵没问题,现在是 513*513 的,里面有好几片联通区域(人像),可能导致递归太深栈溢出了
    magic3584
        12
    magic3584  
    OP
       2023-11-15 09:03:56 +08:00
    @Yuhyeong #9
    不是相同地址,是不同地址但是类似的错 Thread 1: EXC_BAD_ACCESS (code=2,
    应该还是内存问题
    magic3584
        13
    magic3584  
    OP
       2023-11-15 09:06:27 +08:00
    @czfy #10
    您这是 chatGPT 吧。
    **var visited = Set<(Int, Int)>()** swift 没这种写法,所以我改成了用 string
    QingchuanZhang
        14
    QingchuanZhang  
       2023-11-15 11:34:41 +08:00
    为什么不 bfs ?
    magic3584
        15
    magic3584  
    OP
       2023-11-15 11:53:35 +08:00
    @QingchuanZhang #14
    我把 DFS 里 UP 那一行注释掉就好了,不知道为什么。。。
    BFS 的话我得问问 chatGPT
    churchill
        16
    churchill  
       2023-11-15 12:30:29 +08:00
    @magic3584 找联通区域用 BFS 的思路我想不存在栈溢出的问题,吃完饭我来试试
    churchill
        17
    churchill  
       2023-11-15 13:05:14 +08:00
    https://codesandbox.io/s/focused-cloud-zrpxfx
    简单试了下,js 写的,将就看吧
    magic3584
        18
    magic3584  
    OP
       2023-11-15 14:03:33 +08:00
    @churchill #17
    感谢大佬,那个 floodFill 看着有点复杂。。。tmp 怎么只有 push 没有 pop 。。。
    结果就是不知道怎么应用在我这个问题上
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3293 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 12:00 · PVG 20:00 · LAX 04:00 · JFK 07:00
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.