信息学奥赛一本通T1314-过河卒 动态规划

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
// 定义全局变量，包括矩阵大小、中心点坐标和计数器
int n, m, cx, cy, a[30][30] = {0}, num = 0;
int main() {
    // 输入矩阵的大小和中心点的坐标
    cin >> n >> m >> cx >> cy;
    // 将矩阵大小和中心点坐标都增加2，以便处理边界情况
    n += 2;
    m += 2;
    cx += 2;
    cy += 2;
    // 初始化矩阵，设置所有元素为1
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= m; j++) {
            a[i][j] = 1;
        }
    }
    // 设置中心点及其周围的8个点为0
    a[cx][cy] = 0;
    a[cx-2][cy-1] = 0;
    a[cx-1][cy-2] = 0;
    a[cx+2][cy-1] = 0;
    a[cx+1][cy-2] = 0;
    a[cx-2][cy+1] = 0;
    a[cx-1][cy+2] = 0;
    a[cx+2][cy+1] = 0;
    a[cx+1][cy+2] = 0;
    // 设置左上角的点为1，作为路径的起点
    a[2][2] = 1;
    // 动态规划计算从起点到终点的路径数
    for (int x = 2; x <= n; x++) {
        for (int y = 2; y <= m; y++) {
            // 如果当前点是起点或被设置为0，则跳过
            if ((x == 2 && y == 2) || a[x][y] == 0) {
                continue;
            }
            // 否则，当前点的路径数等于其上方和左方的路径数之和
            a[x][y] = a[x-1][y] + a[x][y-1];
        }
    }
    // 输出从起点到终点的路径数
    cout << a[n][m] << endl;
    return 0;
}