解题思路

这是一个动态规划问题，需要考虑马的控制点：

  1. 首先计算出马的所有控制点：
    • 马的位置
    • 所有满足 且 的点
  2. 定义 表示从 到 的路径数
  3. 状态转移方程：
    • 如果 不是马的控制点：
    • 如果 是马的控制点：
  4. 边界条件：（如果起点不是马的控制点）

代码

#include <iostream>
#include <vector>
#include <set>
using namespace std;

bool isHorseControl(int i, int j, int x, int y) {
    if(i == x && j == y) return true;
    int dx = abs(i - x);
    int dy = abs(j - y);
    return (dx + dy == 3) && dx != 0 && dy != 0;
}

long long getPathNum(int n, int m, int x, int y) {
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, 0));
    
    // 初始化起点
    dp[0][0] = isHorseControl(0, 0, x, y) ? 0 : 1;
    
    // 填充第一行和第一列
    for(int i = 1; i <= n; i++) {
        if(!isHorseControl(i, 0, x, y)) {
            dp[i][0] = dp[i-1][0];
        }
    }
    for(int j = 1; j <= m; j++) {
        if(!isHorseControl(0, j, x, y)) {
            dp[0][j] = dp[0][j-1];
        }
    }
    
    // 填充dp数组
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(!isHorseControl(i, j, x, y)) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
    }
    
    return dp[n][m];
}

int main() {
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    cout << getPathNum(n, m, x, y) << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static boolean isHorseControl(int i, int j, int x, int y) {
        if(i == x && j == y) return true;
        int dx = Math.abs(i - x);
        int dy = Math.abs(j - y);
        return (dx + dy == 3) && dx != 0 && dy != 0;
    }
    
    public static long getPathNum(int n, int m, int x, int y) {
        long[][] dp = new long[n + 1][m + 1];
        
        // 初始化起点
        dp[0][0] = isHorseControl(0, 0, x, y) ? 0 : 1;
        
        // 填充第一行和第一列
        for(int i = 1; i <= n; i++) {
            if(!isHorseControl(i, 0, x, y)) {
                dp[i][0] = dp[i-1][0];
            }
        }
        for(int j = 1; j <= m; j++) {
            if(!isHorseControl(0, j, x, y)) {
                dp[0][j] = dp[0][j-1];
            }
        }
        
        // 填充dp数组
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(!isHorseControl(i, j, x, y)) {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        
        return dp[n][m];
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int x = sc.nextInt();
        int y = sc.nextInt();
        System.out.println(getPathNum(n, m, x, y));
        sc.close();
    }
}

def is_horse_control(i, j, x, y):
    if i == x and j == y:
        return True
    dx = abs(i - x)
    dy = abs(j - y)
    return (dx + dy == 3) and dx != 0 and dy != 0

def get_path_num(n, m, x, y):
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    # 初始化起点
    dp[0][0] = 0 if is_horse_control(0, 0, x, y) else 1
    
    # 填充第一行和第一列
    for i in range(1, n + 1):
        if not is_horse_control(i, 0, x, y):
            dp[i][0] = dp[i-1][0]
    for j in range(1, m + 1):
        if not is_horse_control(0, j, x, y):
            dp[0][j] = dp[0][j-1]
    
    # 填充dp数组
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if not is_horse_control(i, j, x, y):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    return dp[n][m]

n, m, x, y = map(int, input().split())
print(get_path_num(n, m, x, y))

算法及复杂度

  • 算法：动态规划
  • 时间复杂度：，需要填充整个 数组
  • 空间复杂度：，需要一个二维 数组