Aha! Algorithms - Floodfill

《啊哈！算法》第 4 章第 5 节，漫水填充法的 Swift 实现。

问题

给一个群岛地图中不同的岛屿填充不同的颜色，并统计地图中有多少个小岛。

解决

遍历每个点，并对与该点临近的点采用深度优先搜索算法进行填充。

// 0 = 海洋；1～9 = 陆地
var a =    [[1, 2, 1, 0, 0, 0, 0, 0, 2, 3],
            [3, 0, 2, 0, 1, 2, 1, 0, 1, 2],
            [4, 0, 1, 0, 1, 2, 3, 2, 0, 1],
            [3, 2, 0, 0, 0, 1, 2, 4, 0, 0],
            [0, 0, 0, 0, 0, 0, 1, 5, 3, 0],
            [0, 1, 2, 1, 0, 1, 5, 4, 3, 0],
            [0, 1, 2, 3, 1, 3, 6, 2, 1, 0],
            [0, 0, 3, 4, 8, 9, 7, 5, 0, 0],
            [0, 0, 0, 3, 7, 8, 6, 0, 1, 2],
            [0, 0, 0, 0, 0, 0, 0, 0, 1, 0]]

let n = a.count //行，纵向为 X 轴
let m = a[0].count //列，横向为 Y 轴

//坐标的改变表示探索方向
let next = [[0, 1],  //x 不变，y + 1，向右走
    [1, 0],  //y 不变，x + 1，向下走
    [0, -1], //向左走
    [-1, 0]] //向上走

//假设地图面积不超过 50 X 50，初始化一个二维数组用于保存走过的地方
var tmp = [Int](repeatElement(0, count: 50))
var book = [[Int]](repeatElement(tmp, count: 50))

func dfs(x: Int, y: Int, color: Int){
    a[x][y] = color

    for k in 0...3 {
        let tx = x + next[k][0]
        let ty = y + next[k][1]
        
        if tx < 0 || tx >= n || ty < 0 || ty >= m{
            continue
        }
        
        //判断是否陆地并且还未标记过
        if a[tx][ty] > 0 && book[tx][ty] == 0{
            book[tx][ty] = 1 //标记已走过这个点
            dfs(x: tx, y: ty, color: color) //尝试下一个点
        }
    }   
}

var sum = 0
var color = 0

for i in 0..<n {
    for j in 0..<m {
        if a[i][j] > 0 {
            sum += 1
            color -= 1 //每个岛用不同的颜色编号
            book[i][j] = 1
            dfs(x: i, y: j, color: color)
        }
    }
}

//输出着色后的地图
for i in 0..<n {
    for j in 0..<m {
        let c = a[i][j]
        let s = (c == 0) ? " \(a[i][j])" : "\(a[i][j])"
        print(s, separator: "", terminator: " ")
    }
    print("\n")
}

//输出小岛个数
print("有 \(sum) 个小岛")

输出

-1  0 -1  0 -3 -3 -3  0 -2 -2 

-1  0 -1  0 -3 -3 -3 -3  0 -2 

-1 -1  0  0  0 -3 -3 -3  0  0 

 0  0  0  0  0  0 -3 -3 -3  0 

 0 -3 -3 -3  0 -3 -3 -3 -3  0 

 0 -3 -3 -3 -3 -3 -3 -3 -3  0 

 0  0 -3 -3 -3 -3 -3 -3  0  0 

 0  0  0 -3 -3 -3 -3  0 -4 -4 

 0  0  0  0  0  0  0  0 -4  0 

有 4 个小岛

代码在 GitHub