#include <stdio.h>
int max(int x,int y){
if (x>y){
return x;
}else{
return y;
}
}
int main(){
int x1,y1,x2,y2;
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
int dp[1+max(x2+4,x1+2)][1+max(y2+4,y1+2)];
int i,n,m;
for (i=3;i<=1+max(x2+4,x1+2);i++){
dp[3][i]=1;
dp[i][3]=1;
}
dp[x2+2][y2+2]=0;
dp[x2+1][y2]=0;
dp[x2][y2+1]=0;
dp[x2+3][y2+2-2]=0;
dp[x2+2-2][y2+2+1]=0;
dp[x2+2-1][y2+2+2]=0;
dp[x2+2+2][y2+2-1]=0;
dp[x2+2+2][y2+2+1]=0;
dp[x2+2+1][y2+2+2]=0;
for(n=4;n<=1+max(x2+4,x1+2);n++){
for(m=4;m<=1+max(y2+4,y1+2);m++){
if (dp[n][m]!=0){
continue;
}
dp[n][m]=dp[n-1][m]+dp[n][m-1];
}
}
printf("%d",dp[2+x1][2+y1]);
return 0;
}
dp[i][j]表示从1.1走到i-2,j-2路线数，会避免马跳道的位置超出范围，所以我把整张二维数组扩充了两行两列。
引用 皆我百晓生 小程序回复内容作答：
过河卒这个题目可以使用动态规划来解决。首先在定义一个二维数组dp[i][j]，表示从(1,1)走到(i,j)的路线数。其中(1,1)表示起始位置，(i,j)表示终点位置。
首先初始化dp数组，将dp数组的左上角(1,1)和终点位置(x2+2, y2+2)设为0，表示起点和终点都不能经过。
然后，从起点开始往右和往下遍历dp数组，求解dp[i][j]。对于每个位置(i,j)，如果此位置是马跳道，即dp[i][j]为0。否则，dp[i][j]的值为其左边位置dp[i-1][j]和上边位置dp[i][j-1]的和，表示可以通过向右或向下一步到达该位置。
最后，输出dp[x1+2][y1+2]，表示从起点(x1, y1)走到终点的路线数。
以下是修改后的代码：
#include <stdio.h>
int max(int x, int y) {
return x > y ? x : y;
}
int main() {
int x1, y1, x2, y2;
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
int dp[105][105];
for (int i = 0; i <= max(x2 + 4, x1 + 2); i++) {
for (int j = 0; j <= max(y2 + 4, y1 + 2); j++) {
if (i == x1 + 2 && j == y1 + 2) {
dp[i][j] = 1;
} else if ((i == x2 + 2 && j == y2 + 2) ||
(i == x2 + 1 && j == y2) ||
(i == x2 && j == y2 + 1) ||
(i == x2 + 3 && j == y2 - 2) ||
(i == x2 - 2 && j == y2 + 3) ||
(i == x2 - 1 && j == y2 + 4) ||
(i == x2 + 4 && j == y2 - 1) ||
(i == x2 + 4 && j == y2 + 1) ||
(i == x2 + 3 && j == y2 + 4)) {
dp[i][j] = 0;
} else {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
printf("%d\n", dp[x2+2][y2+2]);
return 0;
}
注意：这里的dp数组大小需要根据输入的最大值来确定，本例中假设最大为100，所以定义了105x105的数组。如果输入值可能更大，请相应调整数组的大小。另外，这里添加了一个边界条件判断，因为马跳道的位置超出了范围，所以在计算之前将其设为0。
【以下回答由 GPT 生成】
问题优化 标题： 过河卒（Problem 1002）解答 标签： C语言
问题内容：
#include <stdio.h>
int max(int x,int y){
if (x>y){
return x;
}else{
return y;
}
}
int main(){
int x1,y1,x2,y2;
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
int dp[1+max(x2+4,x1+2)][1+max(y2+4,y1+2)];
int i,n,m;
for (i=3;i<=1+max(x2+4,x1+2);i++){
dp[3][i]=1;
dp[i][3]=1;
}
dp[x2+2][y2+2]=0;
dp[x2+1][y2]=0;
dp[x2][y2+1]=0;
dp[x2+3][y2+2-2]=0;
dp[x2+2-2][y2+2+1]=0;
dp[x2+2-1][y2+2+2]=0;
dp[x2+2+2][y2+2-1]=0;
dp[x2+2+2][y2+2+1]=0;
dp[x2+2+1][y2+2+2]=0;
for(n=4;n<=1+max(x2+4,x1+2);n++){
for(m=4;m<=1+max(y2+4,y1+2);m++){
if (dp[n][m]!=0){
continue;
}
dp[n][m]=dp[n-1][m]+dp[n][m-1];
}
}
printf("%d",dp[2+x1][2+y1]);
return 0;
}
dp[i][j]表示从1.1走到i-2,j-2路线数，会避免马跳道的位置超出范围，所以我把整张二维数组扩充了两行两列。
优化后的问题： 过河卒（Problem 1002）解答
问题描述： 过河卒是一道典型的动态规划题目，要求计算卒从起点(x1, y1)到达终点(x2, y2)的方案数。卒的移动规则是只能向右或向下移动，同时马在制约他的位置也需要避开，马在位置(x2+2, y2+2)、(x2+1, y2)、(x2, y2+1)、(x2+3, y2-2)、(x2-2, y2+1)、(x2-1, y2+2)、(x2+2, y2-1)、(x2+2, y2+1)、(x2+1, y2+2)上都不可移动。
以下是优化后的解答，请按照以下步骤进行操作：
解决方案：
首先，我们定义一个max函数用来返回两个数中的较大值。我们将使用这个函数来确定dp数组的大小。 c int max(int x, int y) { if (x > y) { return x; } else { return y; } }
在主函数main中，我们需要读取用户输入的起点和终点坐标。使用scanf函数分别读取x1、y1、x2、y2的值。 c int main() { int x1, y1, x2, y2; scanf("%d %d %d %d", &x1, &y1, &x2, &y2); ... }
接下来，我们定义一个二维数组dp来表示从起点到终点的方案数。根据输入的终点坐标和max函数，我们可以确定dp数组的大小。 c int dp[1 + max(x2 + 4, x1 + 2)][1 + max(y2 + 4, y1 + 2)];
我们接下来需要初始化dp数组。根据题目给出的规则，我们将dp数组的第三行和第三列的值设为1。 c for (int i = 3; i <= 1 + max(x2 + 4, x1 + 2); i++) { dp[3][i] = 1; dp[i][3] = 1; }
根据题目给出的规则，我们还需要将dp数组的一些特定位置的值设为0。例如，dp[x2+2][y2+2]、dp[x2+1][y2]、dp[x2][y2+1]等等。请根据题目要求在代码中添加这些赋值语句。 c dp[x2+2][y2+2] = 0; dp[x2+1][y2] = 0; dp[x2][y2+1] = 0; ...
接下来，我们使用两个循环来计算dp数组中的其他元素。在这两个循环中，我们需要检查dp数组中当前位置的值是否为0，如果不为0，则说明当前位置已经被马占据，无法到达该位置。在这种情况下，我们需要跳过当前位置的计算。否则，我们将使用递推关系dp[n][m] = dp[n-1][m] + dp[n][m-1]计算当前位置的方案数。 c for (int n = 4; n <= 1 + max(x2 + 4, x1 + 2); n++) { for (int m = 4; m <= 1 + max(y2 + 4, y1 + 2); m++) { if (dp[n][m] != 0) { continue; } dp[n][m] = dp[n - 1][m] + dp[n][m - 1]; } }
最后，我们输出dp[2 + x1][2 + y1]，即起点到达终点的方案数。 c printf("%d", dp[2 + x1][2 + y1]);
至此，我们完成了对Problem 1002的解答。请按照以上步骤进行操作，并根据实际情况调整代码。
如果你对这个问题有任何疑问，请随时询问。如果这个问题超出了我的能力范围，请告诉我。
【相关推荐】