欢迎光临散文网 会员登陆 & 注册

2021-02-22:一个象棋的棋盘,然后把整个棋盘放入第一象限,棋

2021-02-22 22:00 作者:福大大架构师每日一题  | 我要投稿

2021-02-22:一个象棋的棋盘,然后把整个棋盘放入第一象限,棋盘的最左下角是(0,0)位置,那么整个棋盘就是横坐标上9条线、纵坐标上10条线的区域。给你三个 参数 x,y,k。返回“马”从(0,0)位置出发,必须走k步。最后落在(x,y)上的方法数有多少种? 

福哥答案2021-02-22:

自然智慧即可。

1.递归。有代码。

2.记忆化搜索。有代码。

3.动态规划。dp是三维数组。棋盘是二维数组,走k步,需要k+1个棋盘。有代码。

4.动态规划,空间压缩。只有相邻棋盘才有依赖,所以只需要用两个棋盘,就能走完。有代码。

代码用golang编写,代码如下:

```go

package main

import "fmt"

func main() {

    a := 3

    b := 4

    k := 5

    fmt.Println("1.递归:", jump1(a, b, k))

    fmt.Println("---")

    fmt.Println("2.记忆化搜索:", jump2(a, b, k))

    fmt.Println("---")

    fmt.Println("3.动态规划:", jump3(a, b, k))

    fmt.Println("---")

    fmt.Println("4.动态规划,空间压缩:", jump4(a, b, k))

}

func jump1(a int, b int, k int) int {

    return process1(0, 0, k, a, b)

}

func process1(x int, y int, rest int, a int, b int) int {

    if x < 0 || x >= 9 || y < 0 || y >= 10 {

        return 0

    }

    if rest == 0 {

        if x == a && y == b {

            return 1

        } else {

            return 0

        }

    }

    ways := process1(x+2, y+1, rest-1, a, b)

    ways += process1(x+2, y-1, rest-1, a, b)

    ways += process1(x-2, y+1, rest-1, a, b)

    ways += process1(x-2, y-1, rest-1, a, b)

    ways += process1(x+1, y+2, rest-1, a, b)

    ways += process1(x+1, y-2, rest-1, a, b)

    ways += process1(x-1, y+2, rest-1, a, b)

    ways += process1(x-1, y-2, rest-1, a, b)

    return ways

}

func jump2(a int, b int, k int) int {

    dp := make([][][]int, 10)

    for i := 0; i < 10; i++ {

        dp[i] = make([][]int, 9)

        for j := 0; j < 9; j++ {

            dp[i][j] = make([]int, k+1)

            for m := 0; m < k+1; m++ {

                dp[i][j][m] = -1

            }

        }

    }

    return process2(0, 0, k, a, b, dp)

}

func process2(x int, y int, rest int, a int, b int, dp [][][]int) int {

    if x < 0 || x >= 10 {

        return 0

    }

    if y < 0 || y >= 9 {

        return 0

    }

    if dp[x][y][rest] != -1 {

        return dp[x][y][rest]

    }

    if rest == 0 {

        if x == a && y == b {

            dp[x][y][rest] = 1

            return 1

        } else {

            dp[x][y][rest] = 0

            return 0

        }

    }

    ways := process2(x+2, y+1, rest-1, a, b, dp)

    ways += process2(x+2, y-1, rest-1, a, b, dp)

    ways += process2(x-2, y+1, rest-1, a, b, dp)

    ways += process2(x-2, y-1, rest-1, a, b, dp)

    ways += process2(x+1, y+2, rest-1, a, b, dp)

    ways += process2(x+1, y-2, rest-1, a, b, dp)

    ways += process2(x-1, y+2, rest-1, a, b, dp)

    ways += process2(x-1, y-2, rest-1, a, b, dp)

    dp[x][y][rest] = ways

    return ways

}

func jump3(a int, b int, k int) int {

    dp := make([][][]int, 10)

    for i := 0; i < 10; i++ {

        dp[i] = make([][]int, 9)

        for j := 0; j < 9; j++ {

            dp[i][j] = make([]int, k+1)

        }

    }

    dp[a][b][0] = 1

    for rest := 1; rest <= k; rest++ {

        for x := 0; x < 10; x++ {

            for y := 0; y < 9; y++ {

                ways := pick3(x+2, y+1, rest-1, dp)

                ways += pick3(x+1, y+2, rest-1, dp)

                ways += pick3(x-1, y+2, rest-1, dp)

                ways += pick3(x-2, y+1, rest-1, dp)

                ways += pick3(x-2, y-1, rest-1, dp)

                ways += pick3(x-1, y-2, rest-1, dp)

                ways += pick3(x+1, y-2, rest-1, dp)

                ways += pick3(x+2, y-1, rest-1, dp)

                dp[x][y][rest] = ways

            }

        }

    }

    return dp[0][0][k]

}

func pick3(x int, y int, rest int, dp [][][]int) int {

    if x < 0 || x >= 10 || y < 0 || y >= 9 {

        return 0

    }

    return dp[x][y][rest]

}

func jump4(a int, b int, k int) int {

    dp := make([][][]int, 10)

    for i := 0; i < 10; i++ {

        dp[i] = make([][]int, 9)

        for j := 0; j < 9; j++ {

            dp[i][j] = make([]int, 2)

        }

    }

    dp[a][b][0] = 1

    for rest := 1; rest <= k; rest++ {

        for x := 0; x < 10; x++ {

            for y := 0; y < 9; y++ {

                ways := pick4(x+2, y+1, dp)

                ways += pick4(x+1, y+2, dp)

                ways += pick4(x-1, y+2, dp)

                ways += pick4(x-2, y+1, dp)

                ways += pick4(x-2, y-1, dp)

                ways += pick4(x-1, y-2, dp)

                ways += pick4(x+1, y-2, dp)

                ways += pick4(x+2, y-1, dp)

                dp[x][y][1] = ways

            }

        }

        for i := 0; i < 10; i++ {

            for j := 0; j < 9; j++ {

                dp[i][j][0], dp[i][j][1] = dp[i][j][1], 0

            }

        }

    }

    return dp[0][0][0]

}

func pick4(x int, y int, dp [][][]int) int {

    if x < 0 || x >= 10 || y < 0 || y >= 9 {

        return 0

    }

    return dp[x][y][0]

}

```

执行结果如下:

***

[左神java代码](https://github.com/algorithmzuo/algorithmbasic2020/blob/master/src/class20/Code02_HorseJump.java)

[评论](https://user.qzone.qq.com/3182319461/blog/1613948266)


2021-02-22:一个象棋的棋盘,然后把整个棋盘放入第一象限,棋的评论 (共 条)

分享到微博请遵守国家法律