```
/*
* Solutio1. Mine. DFS - O(mn) O(mn)
The basic idea is using DFS to found all independent connecting areas with '1' in a graph.
Time complexity=O(mn), because every point in the grid is only checked once approximately.
*/
func numIslands1(_ grid: [[Character]]) -> Int {
var number = 0
let directions = [CGPoint(x: 0, y: 1), CGPoint(x: 0, y: -1), CGPoint(x: 1, y: 0), CGPoint(x: -1, y: 0)]
if grid.count == 0 || grid[0].count == 0 {
return 0
}
let n = grid.count, m = grid[0].count
let oneGrid = [Bool](repeating: false, count: m)
var visited = [[Bool]](repeating: oneGrid, count: n)
for i in 0 ..< n {
for j in 0 ..< m {
if !visited[i][j] && grid[i][j] == "1" {// Found new island
number += 1
DFS(grid, i, j, &visited, directions)// Use DFS to connect all "1" nodes on this island, mark as visited
}
}
}
return number
}
// DFS on one island
func DFS(_ grid: [[Character]], _ i: Int, _ j: Int, _ visited: inout [[Bool]], _ directions: [CGPoint]) {
if i < 0 || i > grid.count - 1 || j < 0 || j > grid[0].count - 1 { return }
if visited[i][j] || grid[i][j] != "1" { return }// Visited
visited[i][j] = true
for direction in directions {// expend on 4 adjacent directions to connect "1" nodes
DFS(grid, i + Int(direction.y), j + Int(direction.x), &visited, directions)
}
}
/*
Solution2. DFS Non-Recursive with Stack - Runtime =O(mn); Space = O(mn) - stack
Set 'v' to visited node in grid, to spare the space for 'visited' array.
*/
func numIslands(_ grid: [[Character]]) -> Int {
if grid.count == 0 {return 0}
var grid = grid
var res = 0, n = grid.count, m = grid[0].count
let directions = [CGPoint(x: 0, y: 1), CGPoint(x: 0, y: -1), CGPoint(x: 1, y: 0), CGPoint(x: -1, y: 0)]
for i in 0 ..< n {
for j in 0 ..< m {
if grid[i][j] == "1" && grid[i][j] != "v" {// Found new island
res += 1
DFS(&grid, i, j, directions)// Use DFS to connect all "1" nodes on this island, mark as visited
}
}
}
return res
}
// DFS on one island
func DFS(_ grid: inout [[Character]], _ iIn: Int, _ jIn: Int, _ directions: [CGPoint]) {// Set 'v' to visited node in grid
var stack = Stack<CGPoint>()
stack.push(CGPoint(x: CGFloat(iIn), y: CGFloat(jIn)))
while !stack.isEmpty() {
let node = stack.pop()!
let i = Int(node.x), j = Int(node.y)
if i < 0 || i > grid.count - 1 || j < 0 || j > grid[0].count - 1 {// Exceed bounds of grids
continue
}
if grid[i][j] == "v" || grid[i][j] == "0" {// Visited or water
continue
}
grid[i][j] = "v"
for direction in directions {// DFS: Extend to 4 directions
let x = CGFloat(i) + direction.x
let y = CGFloat(j) + direction.y
stack.push(CGPoint(x: x, y: y ))
}
}
}
```