目录
牛客_DP13[NOIP2002 普及组]过河卒_路径dp
题目解析
C++代码1
C++代码2
Java代码
牛客_DP13[NOIP2002 普及组]过河卒_路径dp
[NOIP2002 普及组] 过河卒_牛客题霸_牛客网 (nowcoder.com)
描述：
棋盘上 A点有一个过河卒，需要走到目标 B点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示，A 点 (0, 0)、B点(n,m)，同样马的位置坐标是需要给出的。
现在要求你计算出卒从 A点能够到达 B点的路径的条数，假设马的位置(x,y)是固定不动的，并不是卒走一步马走一步。
题目解析
简单路径 dp 问题：相当于是有障碍物的路径类问题，标记走到障碍物上的方法数为 0 即可。
C++代码1
#include <iostream>
#include <ostream>
#include <vector>
using namespace std;
#define int long long // 66666666666666666666666666666666666666666666
signed main()
{// 把马吃了是不是后面的点就能走了？emmmint n = 0, m = 0, x = 0, y = 0;cin >> n >> m >> x >> y;// if (n == 1 || m == 1) // 边界处理// {// cout << 1 << endl;// return 0;// }// if (abs(m - x) + abs(n - y) == 3 && m != x && n != y)// {// cout << 0 << endl;// return 0;// }// vector<vector<int>> borad(n, vector<int>(m));vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));for (int i = 0; i <= n; ++i){if (abs(i - x) + abs(0 - y) == 3 && i != x && 0 != y)break;if (x == i && y == 0) // 马也不能走！！！真服了break;dp[i][0] = 1;}for (int j = 0; j <= m; ++j){if (abs(0 - x) + abs(j - y) == 3 && 0 != x && j != y)break;if (x == 0 && y == j) // 马也不能走！！！真服了break;dp[0][j] = 1;}for (int i = 1; i <= n; ++i){for (int j = 1; j <= m; ++j){if (abs(i - x) + abs(j - y) == 3 && i != x && j != y)continue;if (x == i && y == j) // 马也不能走！！！真服了continue;dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}// for(int i = 0; i <= n; ++i) // DeBug：打印dp矩阵// {// for(int j = 0; j <= m; ++j)// {// cout << dp[i][j] << " ";// }// cout << endl;// }cout << dp[n][m] << endl;return 0;
}C++代码2
#include <iostream>
#include <ostream>
#include <vector>
using namespace std;
#define int long long // 66666666666666666666666666666666666666666666
signed main()
{// 把马吃了是不是后面的点就能走了？emmmint n = 0, m = 0, x = 0, y = 0;cin >> n >> m >> x >> y;// if (n == 1 || m == 1) // 边界处理// {// cout << 1 << endl;// return 0;// }// if (abs(m - x) + abs(n - y) == 3 && m != x && n != y)// {// cout << 0 << endl;// return 0;// }// vector<vector<int>> borad(n, vector<int>(m));vector<vector<int>> dp(n + 2, vector<int>(m + 2, 0));// for (int i = 0; i <= n; ++i)// {// if (abs(i - x) + abs(0 - y) == 3 && i != x && 0 != y)// break;// if (x == i && y == 0) // 马也不能走！！！真服了// break;// dp[i][0] = 1;// }// for (int j = 0; j <= m; ++j)// {// if (abs(0 - x) + abs(j - y) == 3 && 0 != x && j != y)// break;// if (x == 0 && y == j) // 马也不能走！！！真服了// break;// dp[0][j] = 1;// }dp[0][1] = 1;x += 1, y += 1;for (int i = 1; i <= n + 1; ++i){for (int j = 1; j <= m + 1; ++j){if (abs(i - x) + abs(j - y) == 3 && i != x && j != y)continue;if (x == i && y == j) // 马也不能走！！！真服了continue;dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}// for(int i = 0; i <= n; ++i) // DeBug：打印dp矩阵// {// for(int j = 0; j <= m; ++j)// {// cout << dp[i][j] << " ";// }// cout << endl;// }cout << dp[n + 1][m + 1] << endl;return 0;
}Java代码
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt(), m = in.nextInt(), x = in.nextInt(), y = in.nextInt();long[][] dp = new long[n + 2][m + 2];dp[0][1] = 1;x += 1; y += 1;for(int i = 1; i <= n + 1; i++){for(int j = 1; j <= m + 1; j++){if(i != x && j != y && Math.abs(i - x) + Math.abs(j - y) == 3|| (i == x && j == y)){dp[i][j] = 0;}else{dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}}System.out.println(dp[n + 1][m + 1]);}
}
)
