题解 | #学生查询#
[NOIP2002 普及组] 过河卒
http://www.nowcoder.com/practice/cc1a9bc523a24716a117b438a1dc5706
(1)dp数组含义：dp[x][y]表示到达(x, y)的路径条数
(2)递推公式：dp[i][j] = dp[i-1][j] + dp[i][j - 1];(因为卒只可以向右或者向下走)
(3)初始化：dp[0][0] = 1,根据马的坐标(x, y)，可以将(x,y)和马可以到达的八个点的坐标对应dp[ ][ ]改为0，对第一行、第一列进行初始化:dp[0][j] = dp[0][j - 1]、dp[i][0] = dp[i - 1][0]
(2)递推公式：dp[i][j] = dp[i-1][j] + dp[i][j - 1];(因为卒只可以向右或者向下走)
(3)初始化：dp[0][0] = 1,根据马的坐标(x, y)，可以将(x,y)和马可以到达的八个点的坐标对应dp[ ][ ]改为0，对第一行、第一列进行初始化:dp[0][j] = dp[0][j - 1]、dp[i][0] = dp[i - 1][0]
(4)遍历顺序：二重循环，正序遍历
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main() {
int n, m, x, y;
cin >> n >> m >> x >> y;
long long dp[n + 1][m + 1];
memset(dp, -1, sizeof(dp));
dp[0][0] = 1;
if(x <= n && y <= m) {
dp[x][y] = 0;
}
int change[8][2] = {{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};
for(int i = 0; i < 8; ++i) {
int temp_x = x + change[i][0];
int temp_y = y + change[i][1];
if(temp_x >= 0 && temp_y >= 0 && temp_x <= n && temp_y <= m) {
dp[temp_x][temp_y] = 0;
}
}
for(int j = 1; j <= m; ++j) {
if(dp[0][j] != 0) {
dp[0][j] = dp[0][j - 1];
}
}
for(int i = 1; i <= n; ++i) {
if(dp[i][0] != 0) {
dp[i][0] = dp[i - 1][0];
}
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(dp[i][j] != 0) { //可能是马可以到达的点
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
cout << dp[n][m] << endl;
return 0;
}
查看14道真题和解析
投递OPPO等公司10个岗位 >