題目
地上有一個(gè)m行n列的方格命斧，一個(gè)機(jī)器人從坐標(biāo) 的格子開(kāi)始移動(dòng)田晚，它每次可以向左，右国葬，上贤徒，下移動(dòng)一格，但不能進(jìn)入行坐標(biāo)和列坐標(biāo)的位數(shù)之和大于
的格子汇四。例如接奈，當(dāng)
為18時(shí)，機(jī)器人能夠進(jìn)入方格
,因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=3%2B5%2B3%2B7%3D18" alt="3+5+3+7=18" mathimg="1">通孽。但它不能進(jìn)入方格
序宦。因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=3%2B5%2B3%2B8%3D19" alt="3+5+3+8=19" mathimg="1">。請(qǐng)問(wèn)該機(jī)器人能夠到達(dá)多少個(gè)格子背苦？
思路
可以把方格看做一個(gè)的矩陣互捌。在這個(gè)矩陣中堡僻，除邊界以外的格子之外，其他格子都有四個(gè)相鄰的格子疫剃。
- 機(jī)器人從坐標(biāo)
開(kāi)始移動(dòng)
- 當(dāng)機(jī)器人準(zhǔn)備進(jìn)入到
時(shí)钉疫，判斷機(jī)器人能否進(jìn)入到該格子
- 判斷機(jī)器人是否能進(jìn)入格子的條件是，行和列的位數(shù)之和小于k巢价，并且機(jī)器人也沒(méi)有進(jìn)入過(guò)次格子
- 若不能進(jìn)入牲阁，則不去嘗試進(jìn)入到它周?chē)母褡印?/li>
- 若能進(jìn)入，則讓機(jī)器人分別去嘗試進(jìn)入它周?chē)乃膫€(gè)格子
,而由于格子是從
。也就是回到第2步碉克。
代碼實(shí)現(xiàn)（Swift）
首先用結(jié)構(gòu)體Grid來(lái)表示m行n列的方格
//用來(lái)表示每個(gè)格子的坐標(biāo)
typealias Coordinate = (row:Int,column:Int)
struct Grid {
let row : Int //行數(shù)
let column : Int //列數(shù)
//原點(diǎn)坐標(biāo)
var originCoordinate : Coordinate {
return (row:0,column:0)
}
//在方格內(nèi)指定坐標(biāo)的上面的格子凌唬，若上面已沒(méi)有格子，則返回nil
func above(coor:Coordinate) -> Coordinate? {
if coor.row >= 0 && coor.row < row - 1 && coor.column >= 0 && coor.column < column{
return (row:coor.row + 1,column:coor.column)
}
return nil
}
//在方格內(nèi)指定坐標(biāo)的下面的格子漏麦，若下面已沒(méi)有格子客税，則返回nil
func below(coor:Coordinate) -> Coordinate? {
if coor.row > 0 && coor.row < row && coor.column >= 0 && coor.column < column{
return (row:coor.row - 1,column:coor.column)
}
return nil
}
//在方格內(nèi)指定坐標(biāo)的左面的格子，若左面已沒(méi)有格子撕贞，則返回nil
func left(coor:Coordinate) -> Coordinate? {
if coor.row >= 0 && coor.row < row && coor.column > 0 && coor.column < column{
return (row:coor.row,column:coor.column - 1)
}
return nil
}
//在方格內(nèi)指定坐標(biāo)的右面的格子更耻，若右面已沒(méi)有格子，則返回nil
func right(coor:Coordinate) -> Coordinate? {
if coor.row >= 0 && coor.row < row && coor.column >= 0 && coor.column < column - 1{
return (row:coor.row,column:coor.column + 1)
}
return nil
}
}
然后在用結(jié)構(gòu)體Robot來(lái)表示機(jī)器人
struct Robot {
let k : Int
let grid : Grid //格子
init(k :Int, grid: Grid) {
self.k = k
self.grid = grid
}
//對(duì)外暴露的方法捏膨，做了一些數(shù)據(jù)的初始化和邊界的判斷秧均。內(nèi)部調(diào)用了private func movingCount(coor:Coordinate? , visited:inout [Bool]) -> Int
func movingCount() -> Int {
guard k >= 0, grid.column > 0, grid.row > 0 else { return 0 }
var visited = Array(repeating: false, count: grid.row * grid.column)
let count = movingCount(coor: grid.originCoordinate , visited : &visited)
return count
}
//實(shí)現(xiàn)上面的思路
private func movingCount(coor:Coordinate? , visited:inout [Bool]) -> Int {
if let coor = coor , isVaild(coor: coor, visited: visited) {
visited[coor.row * grid.column + coor.column] = true
return 1 + movingCount(coor:grid.above(coor: coor), visited: &visited)
+ movingCount(coor:grid.right(coor: coor), visited: &visited)
}
return 0
}
//用來(lái)判斷是否能進(jìn)入到此格子
private func isVaild(coor:Coordinate , visited : [Bool]) -> Bool {
return visited[coor.row * grid.column + coor.column] == false && (digitsSum(number: coor.row) + digitsSum(number: coor.column) <= k)
}
//求一個(gè)數(shù)字的位數(shù)之和
private func digitsSum(number:Int) -> Int {
var sum = 0
var topDigit = number
while topDigit > 0 {
sum += topDigit % 10
topDigit = topDigit / 10
}
return sum
}
}
Test
let grid = Grid(row: 100, column: 100)
for i in -2...30 {
let robot = Robot(k: i, grid : grid)
let count = robot.movingCount()
print("\(i)===\(count)")
}
