P1002

思路 设 \(dp_{i,j}\) 表示第 \(i\) 行 \(j\) 列卒走到这里有多少种方式。 卒是可以向右和下走，所以到这个点只能从左或上来，不难得出转移公式：\(dp_{i,j} = dp_{i-1,j}+dp_{i,j-1}\)。 如果马在这个点上或者说马能到这个点上，那么卒不能到这个点， ......

[NOIP2002 普及组] 过河卒 题目描述 棋盘上 \(A\) 点有一个过河卒，需要走到目标 \(B\) 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 \(C\) 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。 棋盘用坐标表示，\(A\) ......

给出的地图从(0,0)开始，先将地图向右下方偏移，使原点变为(1,1) cin >> n >> m >> x >> y; m++, n++, x++, y++;//将地图向右下方偏移,让地图原点变为(0,0) 读入马的坐标后标记出所有马能走的坐标，剩下的点就是卒能走到的点 设状态dp(i,j)为从( ......

P1002 [NOIP2002 普及组] 过河卒 基础DP 卒只能向右/向下 由此可得转移方程 dp[i][j] = dp[i -1][j] + dp[i][j - 1] 卒不能走马能到的地方和马所在的地方 则用一个数组标记马能到的地方和马所在的地方，在经过该点的时候跳过即可 注意判断边界问题以及d ......

原题链接 解题思路 这是一道经典的动态规划题目。 如果尝试使用深度优先搜索（dfs）或广度优先搜索（bfs）做就会获得 TLE （注意数据范围）。于是我们想到了更为高级的动态规划（Dynamic Programming, dp）。 简略介绍动态规划算法的核心思想：把原问题分解为相对简单的子问题的方式 ......

[过河卒](https://www.luogu.com.cn/problem/P1002 "过河卒") ## 题目描述 棋盘上 $A$ 点有一个过河卒，需要走到目标 $B$ 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 $C$ 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控 ......

思路： 1.标记马点 z[i][[j]=0 2.正常 z[i][j]=z[i-1][j]+z[i][j-1] #include<iostream> using namespace std; int n,m,a,b; long long ma[30][30],bck[30][30]; int dx[8 ......