动态规划——马儿跳
2021/11/6 6:12:31
本文主要是介绍动态规划——马儿跳,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
/* 马儿跳问题 马走日 9*10的棋盘,马在左下角, 给定任意一个位置,一个步数k,问,马跳到该点,用k步的方法有多少种 k (x,y) */ /* 9 *----*----*----*----*----*----*----*----* | | | | \ | / | | | | 8 *----*----*----*----*----*----*----*----* | | | | / | \ | | | | 7 *----*----*----*----*----*----*----*----* | | | | | | | | | 6 *----*----*----*----*----*----*----*----* | | | | | | | | | 5 *----*----*----*----*----*----*----*----* | 楚 河 汉 界 | 4 *----*----*----*----*----*----*----*----* | | | | | | | | | 3 *----*----*----*----*----*----*----*----* | | | | | | | | | 2 *----*----*----*----*----*----*----*----* | | | | \ | / | | | | 1 *----*----*----*----*----*----*----*----* | | | | / | \ | | | | 0 *----*----*----*----*----*----*----*----* 0 1 2 3 4 5 6 7 8 */ func HorseJump(targetX, targetY, curX, curY, rest int) int { if curX < 0 || curX > 9 || curY < 0 || curY > 8 || rest < 0 { return 0 } if rest == 0 { if curX == targetX && curY == targetY { return 1 }else { return 0 } } //八个方向 ans := 0 for _, direction := range [][]int{{+2,+1},{+1,+2},{-1,+2},{-2,+1},{-2,-1},{-1,-2},{+1,-2},{+2,-1}}{ ans += HorseJump(targetX, targetY, curX + direction[0], curY+direction[1],rest - 1) } return ans } func HorseJumpForDp(targetX, targetY, k int) int { dp := make([][][]int,10) for i := range dp { dp[i] = make([][]int,9) for w := range dp[i] { dp[i][w] = make([]int,k+1) } } dp[0][0][0] = 1 for level := 1; level <= k; level++ { for i := 0; i < 10; i++ { for j := 0; j < 9; j++ { ans := 0 for _, direction := range [][]int{{+2,+1},{+1,+2},{-1,+2},{-2,+1},{-2,-1},{-1,-2},{+1,-2},{+2,-1}}{ if i + direction[0] < 0 || i + direction[0] > 9 || j+direction[1] < 0 || j+direction[1] > 8 { continue } ans += dp[i + direction[0]][j + direction[1]][level-1] } dp[i][j][level] = ans } } } return dp[targetX][targetY][k] } func TestHoursJump(t *testing.T) { //fmt.Println(HourseJump(3,2,0,0,3)) fmt.Println(HorseJump(6,8,0,0,10)) fmt.Println(HorseJumpForDp(6,8,10)) }
这篇关于动态规划——马儿跳的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南
- 2024-09-26Springboot微服务资料入门教程