題目

地上有一個m行n列的方格，一個機器人從坐標 的格子開始移動，它每次可以向左，右，上，下移動一格，但不能進入行坐標和列坐標的位數(shù)之和大于的格子。例如，當 為18時，機器人能夠進入方格,因為。但它不能進入方格。因為。請問該機器人能夠到達多少個格子？

思路

可以把方格看做一個的矩陣。在這個矩陣中，除邊界以外的格子之外，其他格子都有四個相鄰的格子。

1. 機器人從坐標開始移動
2. 當機器人準備進入到時，判斷機器人能否進入到該格子
3. 判斷機器人是否能進入格子的條件是，行和列的位數(shù)之和小于k，并且機器人也沒有進入過次格子
4. 若不能進入，則不去嘗試進入到它周圍的格子。
5. 若能進入，則讓機器人分別去嘗試進入它周圍的四個格子,而由于格子是從開始的，只需要向上和向右就能進入到所有能到達的格子，所以只需讓機器人分別去嘗試進入它上面或右面的格子 。也就是回到第2步。

代碼實現(xiàn)（Swift）

首先用結(jié)構(gòu)體Grid來表示m行n列的方格

//用來表示每個格子的坐標
typealias Coordinate = (row:Int,column:Int)
struct Grid {
    let row : Int //行數(shù)
    let column : Int //列數(shù)
    //原點坐標
    var originCoordinate : Coordinate {
        return (row:0,column:0)
    }
    //在方格內(nè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)指定坐標的下面的格子，若下面已沒有格子，則返回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)指定坐標的左面的格子，若左面已沒有格子，則返回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)指定坐標的右面的格子，若右面已沒有格子，則返回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來表示機器人

struct Robot {
    let k : Int
    let grid : Grid //格子
  
    init(k :Int, grid: Grid) {
        self.k = k
        self.grid = grid
    }
    
    //對外暴露的方法，做了一些數(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
    }
    
    //實現(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
    }
    
    //用來判斷是否能進入到此格子
    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)
    }
    
    //求一個數(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)")
}