This is a problem I encountered during my summer vacation while trying to solve problems on Luogu. After quickly finishing the first problem, A+B, which was as simple as elementary school math, I thought this was the beginning of my dream. However, the second problem, the River Crossing Pawn, gave me a rude awakening. Perhaps I had been away from programming problems for too long, as I was at a loss facing the screen full of errors, and I didn’t think about it further. Recently, I came across a video related to this problem on Bilibili, and I will attempt a different solution again. Below is the source of the problem statement and the problem itself.https://www.luogu.com.cn/problem/P1002
Previous Approach:
It can be seen that the writing is very messy and hasty. My thought at the time was: isn’t it just a simple enumeration algorithm that can solve it? Since the pawn can only move right or down, I let it move right until it hits a knight’s point or the edge of the board, then move down. If moving down is blocked, I would switch to the next row. Thus, I would traverse down m times from the first row (the coordinates of B are (n,m)), and when encountering a knight’s point, I would try to move right until reaching point B. Finally, I introduced the knight’s point (x,y) and the eight points that the knight can jump to: a[x+2][y+1] and a[x+1][y+2]. At the same time, I also had to consider the knight’s points and the boundaries. Just when I thought this could work, it still resulted in an error.Error Reason: The enumeration data is too large and misses many valid paths. If I enumerate like this, assuming the chessboard is 20*20, then according to the formula$C_{n+m}^{m}$, it can be calculated that there will be 137,846,528,820 paths, which greatly exceeds our memory requirements and computational speed, so this method has already been discarded.How should I correct my previous approach?
First, we observe the chessboard: Since from A (0,0) to point a, there are only two paths: first right then down, or first down then right. That is to say, the path from A to the point above a has only one way to go right, and the path from A to the left of a has only one way to go down. This means that the number of paths from A to a equals the number of paths from A to (1,0) and from A to (0,1). From this pattern, we can see that the number of paths from A to point d equals the number of paths from A to a plus the number of paths from A to c.Thus, we have derived a recurrence relation:a[i][j]=a[i-1][j]+a[i][j-1]Then we set all accessible cells on the chessboard to 1 and inaccessible cells to 0, meaning that all cells related to the knight’s points are marked as 0.First, implement the code without knight’s points:
#include int main() { int a[30][30] = {0}; int n, m,x,y; std::cin >> n >> m; for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { if (i==0&&j==0){ continue; } if (i==0||j==0){ a[i][j] = 1; } else { a[i][j] = a[i - 1][j] + a[i][j - 1]; } } } std::cout<<a[n][m]; 0;}</a>Now add the eight knight’s points:
The knight’s points must be within the chessboard and boundary range, meaning that points within the chessboard must be marked as 0.So
if (x+2<=n&&y-1>=0){a[x+2][y-1]=0;}if (x+2<=n&&y+1<=m){a[x+2][y+1]=0;}if (x-2>=0&&y-1>=0){a[x-2][y-1]=0;}if (x-2>=0&&y+1<=m){a[x-2][y+1]=0;}if (x+1<=n&&y+2<=m){a[x+1][y+2]=0;}if (x+1<=n&&y-2>=0){a[x+1][y-2]=0;}if (x-1>=0&&y+2<=m){a[x-1][y+2]=0;}if (x-1>=0&&y-2>=0){a[x-1][y-2]=0;}Check each of the eight points, integrate the code, and form the complete code:
#include int main() { int a[30][30] = {0}; int n, m,x,y; std::cin >> n >> m>>x>>y; for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { a[i][j] = 1; } } a[x][y] = 0; if (x+2<=n&&y-1>=0){a[x+2][y-1]=0;} if (x+2<=n&&y+1<=m){a[x+2][y+1]=0;} if (x-2>=0&&y-1>=0){a[x-2][y-1]=0;} if (x-2>=0&&y+1<=m){a[x-2][y+1]=0;} if (x+1<=n&&y+2<=m){a[x+1][y+2]=0;} if (x+1<=n&&y-2>=0){a[x+1][y-2]=0;} if (x-1>=0&&y+2<=m){a[x-1][y+2]=0;} if (x-1>=0&&y-2>=0){a[x-1][y-2]=0;} for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { if (i==0&&j==0){// Skip when at the starting point A continue; } if (a[i][j]==0){// Skip when encountering a knight's point continue; } if (i==0){ a[i][j] = a[i][j - 1]; } else if (j==0){ a[i][j] = a[i - 1][j]; } else { a[i][j] = a[i - 1][j] + a[i][j - 1]; } } } std::cout<<a[n][m]; 0;}</a>In lines 30-35, I still do not understand why the number of paths for the first row and the first column equals the number of paths of the previous cell.Reference video:https://www.bilibili.com/video/BV1FC4y1E7BD/?spm_id_from=333.337.search-card.all.click&vd_source=6e24310d9149d3d73e7b80851aae93ee