在那个过河卒逃过了马的控制以超级超级多的走法走到了终点之后,这匹马表示它不开心了…… 于是,终于有一天,它也过河了! 由于过河马积累了许多的怨念,所以这次它过了河之后,再也没有什么东西可以限制它,它可以自由自在的在棋盘上驰骋。一开始,它是在一个n行m列棋盘的左下角(1,1)的位置,它想要走到终点右上角(n,m)的位置。而众所周知,马是要走日子格的。可是这匹马在积累了这么多怨念之后,它再也不想走回头路——也就是说,它只会朝向上的方向跳,不会朝向下的方向跳。 那么,这匹马它也想知道,它想从起点跳到终点,一共有多少种走法呢?算法描述
时间: 2023-03-21 07:02:25 浏览: 166
这是一道典型的动态规划问题。定义一个二维数组dp,其中dp[i][j]表示马从起点(1,1)跳到(i,j)位置的不回头路走法总数。对于每个位置(i,j),它可以由(i-2,j+1)或者(i-1,j+2)两个位置跳过来,因此有状态转移方程:dp[i][j] = dp[i-2][j+1] + dp[i-1][j+2]。
边界条件:dp[1][1] = 1,dp[i][j] = 0(当(i,j)位置超出棋盘范围或者是向下跳)。
最终,dp[n][m]就是马从起点跳到终点的不回头路走法总数。
代码示例(Python):
```python
def horseJump(n, m):
dp = [[0] * (m+1) for _ in range(n+1)]
dp[1][1] = 1
for i in range(1, n+1):
for j in range(1, m+1):
if i >= 2 and j <= m-1:
dp[i][j] = dp[i-2][j+1] + dp[i-1][j+2]
return dp[n][m]
n, m = 8, 8
res = horseJump(n, m)
print(res)
```
相关问题
java 在一个二维数组中,B表示不能通过,K表示可以通过,终点为T,找出所有能走到T的起点
可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来解决这个问题。
首先,我们需要定义一个二维数组来表示地图,并初始化它。在搜索过程中,我们需要记录每个点是否被访问过,可以使用一个布尔类型的二维数组来记录。我们还需要记录所有能够到达终点的起点,可以使用一个列表来存储。
接下来,我们可以从每个起点开始进行深度优先搜索或广度优先搜索。对于每个点,如果它是终点,就将该起点加入到列表中。否则,如果该点可达且未被访问过,则继续搜索。
具体实现可以参考以下代码:
```java
import java.util.ArrayList;
import java.util.List;
public class FindStartingPoints {
private static final int ROW = 5;
private static final int COL = 5;
private static char[][] map = {
{'B', 'B', 'B', 'B', 'B'},
{'B', 'K', 'B', 'K', 'B'},
{'B', 'K', 'B', 'K', 'B'},
{'B', 'K', 'B', 'K', 'B'},
{'B', 'B', 'B', 'B', 'T'}
};
private static boolean[][] visited = new boolean[ROW][COL];
private static List<int[]> startingPoints = new ArrayList<>();
public static void main(String[] args) {
// 遍历所有起点
for (int i = 1; i < ROW - 1; i++) {
for (int j = 1; j < COL - 1; j++) {
if (map[i][j] == 'K') {
dfs(i, j);
}
}
}
// 输出所有能到达终点的起点
System.out.println("Starting points:");
for (int[] point : startingPoints) {
System.out.println("(" + point[0] + ", " + point[1] + ")");
}
}
private static void dfs(int row, int col) {
visited[row][col] = true;
if (map[row][col] == 'T') {
startingPoints.add(new int[]{row, col});
return;
}
if (map[row + 1][col] == 'K' && !visited[row + 1][col]) {
dfs(row + 1, col);
}
if (map[row - 1][col] == 'K' && !visited[row - 1][col]) {
dfs(row - 1, col);
}
if (map[row][col + 1] == 'K' && !visited[row][col + 1]) {
dfs(row, col + 1);
}
if (map[row][col - 1] == 'K' && !visited[row][col - 1]) {
dfs(row, col - 1);
}
visited[row][col] = false;
}
}
```
上述代码使用深度优先搜索来遍历所有起点,对于每个起点,如果它可达终点,则将其加入到列表中。注意需要在搜索结束后将访问记录清除,以便处理下一个起点。
如果要使用广度优先搜索,可以使用队列来存储待访问的点,并在每一层结束后将访问记录清除。
从一行格子上的起点走到终点,每个格子要走两分钟,如何用代码表示出来
可以使用二维列表来表示这个格子迷宫,其中起点用一个特定的字符表示,终点用另一个特定的字符表示,空白格子用另一个字符表示。然后使用一个循环来模拟走路过程,每次循环移动一个位置,直到到达终点。
以下是一个示例代码:
```python
maze = [
['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
['#', 'S', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#'],
['#', '#', '#', '#', '#', '#', '#', '#', ' ', '#'],
['#', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', '#'],
['#', '#', '#', '#', '#', ' ', '#', '#', ' ', '#'],
['#', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#'],
['#', '#', '#', ' ', '#', '#', '#', '#', '#', '#'],
['#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'G', '#'],
['#', '#', '#', '#', '#', '#', '#', '#', '#', '#']
]
start_row, start_col = 1, 1 # 起点坐标
end_row, end_col = 7, 8 # 终点坐标
current_row, current_col = start_row, start_col # 初始化当前坐标
while (current_row, current_col) != (end_row, end_col):
# 根据下一个移动方向计算下一个坐标
next_row, next_col = current_row, current_col + 1 # 向右走
# 判断下一个位置是否可以走
if maze[next_row][next_col] == ' ':
current_row, current_col = next_row, next_col # 更新当前坐标
time.sleep(2) # 等待2秒钟,模拟走路过程
else:
print('无法向右走,尝试其他方向')
print('已到达终点!')
```
在这个例子中,我们使用一个`while`循环来模拟走路过程。在每次循环中,我们计算下一个移动方向(这里示例只考虑向右移动),然后判断下一个位置是否可以走。如果可以走,就更新当前坐标,并等待2秒钟,模拟走路过程。如果下一个位置无法走,就尝试其他方向。当到达终点时,循环结束。