func movingCount(_ m: Int, _ n: Int, _ k: Int) -> Int {
if m <= 0 || n <= 0 || k < 0 {
return 0
}
var flags: [[Bool]] = Array(repeating: Array(repeating: false, count: n), count: m)
return moveTo(0, 0, k, flags: &flags)
}
2.1 核心递归逻辑
func moveTo(_ x: Int, _ y: Int, _ k: Int, flags: inout [[Bool]]) -> Int {
if (x < 0 || x >= flags.first?.count ?? 0) ||
(y < 0 || y >= flags.count) ||
(flags[y][x] == true) ||
(digitSum(x) + digitSum(y) > k)
{
return 0
}
flags[y][x] = true
let count = 1
+ moveTo(x + 1, y, k, flags: &flags)
+ moveTo(x - 1, y, k, flags: &flags)
+ moveTo(x, y + 1, k, flags: &flags)
+ moveTo(x, y - 1, k, flags: &flags)
return count
}
2.2 数位和函数
func digitSum(_ num: Int) -> Int {
var temp = num
var result = 0
while temp > 0 {
result += temp % 10
temp = Int(floor(Double(temp) / 10.0))
}
return result
}
func movingCount_bfs(_ m: Int, _ n: Int, _ k: Int) -> Int {
var visited = Array(repeating: Array(repeating: false, count: n), count: m)
var result = 0
var queue:Array = [(0,0,0,0)]
while !queue.isEmpty {
let (y,x,si,sj) = queue.removeFirst()
if y >= m || x >= n || k < si + sj || visited[y][x]{
continue
}
visited[y][x] = true
result = result + 1
queue.append((y + 1, x, digitSum(y + 1), sj))
queue.append((y, x + 1, si, digitSum(x + 1)))
}
return result
}