P1002 [NOIP 2002 普及组] 过河卒

张开发
• 2026/4/19 10:04:10 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

P1002 [NOIP 2002 普及组] 过河卒
感觉自己好笨....#include iostreamusing namespace std;// 使用 long long 防止路径数相加时爆 intlong long dp[30][30];bool ctrl[30][30];// 马的 8 个跳跃方向 马自己所在的位置 (0, 0)int dx[] {0, -2, -1, 1, 2, 2, 1, -1, -2};int dy[] {0, 1, 2, 2, 1, -1, -2, -2, -1};int main() {// 优化输入输出ios::sync_with_stdio(false);cin.tie(0);int n, m, x, y;if (!(cin n m x y)) return 0;// 【核心技巧坐标全体平移】// 将整个棋盘向右下平移 2 格起点从 (0,0) 变成 (2,2)n 2; m 2;x 2; y 2;// 标记马的 9 个控制点for (int i 0; i 9; i) {// x dx[i] 是马的新横坐标y dy[i] 是新纵坐标ctrl[x dx[i]][y dy[i]] true;}// 初始化起点走到起点 (2, 2) 只有 1 种方法dp[2][2] 1;// 开始二维递推for (int i 2; i n; i) {for (int j 2; j m; j) {// 起点已经初始化过了跳过if (i 2 j 2) continue;// 如果这个点被马控制了直接视作 0 条路径if (ctrl[i][j] true) {dp[i][j] 0;} else {// 状态转移方程上边过来的路径数 左边过来的路径数dp[i][j] dp[i - 1][j] dp[i][j - 1];}}}// 终点现在是 (n, m)cout dp[n][m] \n;return 0;}

更多文章