DP13. [NOIP2002 普及组] 过河卒
描述
棋盘上 A点有一个过河卒，需要走到目标 B点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
输入描述
仅一行，输入 n,m,x,y 四个正整数。分别表示B点坐标和马的坐标输出描述
示例1
输入:
6 6 3 3
输出:
6
示例2
输入:
5 4 2 3
输出:
3
示例3
输入:
2 5 3 5
输出:
1
C 解法, 执行用时: 2ms, 内存消耗: 312KB, 提交时间: 2022-07-26
#include <stdio.h>
int fun(int x,int y,int n,int m);
int main(){
int n = 0,m = 0,x = 0,y = 0;
scanf("%d %d %d %d",&n,&m,&x,&y);
long dp[n+1][m+1];
for(int i = 0; i < n+1; i++){
for(int j = 0; j < m+1; j++){
if ((abs(i - x) + abs(j - y)) == 3 && i != x && j != y){
dp[i][j] = -1;
}
else
dp[i][j] = 0;
}
}
if (x >= 0 && x <= n && y >= 0 && y <= m)
dp[x][y] = -1;
int i = 0;
int j = 0;
// if(fun(x,y,n,m)) dp[x][y] = -1;
// if(fun(x+2,y+1,n,m)) dp[x+2][y+1] = -1;
// if(fun(x+1,y+2,n,m)) dp[x+1][y+2] = -1;
// if(fun(x-1,y+2,n,m)) dp[x-1][y+2] = -1;
// if(fun(x-2,y+1,n,m)) dp[x-2][y+1] = -1;
// if(fun(x-2,y-1,n,m)) dp[x-2][y-1] = -1;
// if(fun(x-1,y-2,n,m)) dp[x-1][y-2] = -1;
// if(fun(x+1,y-2,n,m)) dp[x+1][y-2] = -1;
// if(fun(x+2,y-1,n,m)) dp[x+2][y-1] = -1;
for(i = 0; i < n+1; i++){
if(dp[i][0] == -1)
break;
dp[i][0] = 1;
}
for(j = 0; j < m+1; j++){
if(dp[0][j] == -1)
break;
dp[0][j] = 1;
}
for(i = 1; i < n+1; i++){
for(j = 1; j < m+1; j++){
if(dp[i][j] == -1 || (dp[i-1][j] == -1 && dp[i][j-1] == -1)){
continue;
}
else if(dp[i-1][j] == -1 && dp[i][j-1] != -1){
dp[i][j] = dp[i][j-1];
}
else if(dp[i-1][j] != -1 && dp[i][j-1] == -1){
dp[i][j] = dp[i-1][j];
}
else{
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
printf("%ld",dp[i-1][j-1]);
return 0;
}
int fun(int x,int y,int n,int m){
if(x >= 0 && x <= n && y >= 0 && y <= m)
return 1;
else
return 0;
}
int abs(int x){
if (x >= 0)
return x;
else
return -1 * x;
}
C++ 解法, 执行用时: 2ms, 内存消耗: 472KB, 提交时间: 2022-06-18
#include<iostream>
using namespace std;
#include<vector>
#include<cmath>
int main(){
int n,m,x,y;
cin>>n>>m>>x>>y;
vector<vector<long long>> dp(n+1,vector<long long>(m+1));
for(int i=0;i<=n;i++){
if(abs(x-i)+abs(y-0)==3&&x!=i&&y!=0||x==i&&y==0)
break;
dp[i][0]=1;
}
for(int j=0;j<=m;j++){
if(abs(x-0)+abs(y-j)==3&&x!=0&&y!=j||x==0&&y==j)
break;
dp[0][j]=1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(abs(x-i)+abs(y-j)==3&&x!=i&&y!=j||x==i&&y==j)
continue;
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
cout<<dp[n][m]<<endl;
return 0;
}
C 解法, 执行用时: 3ms, 内存消耗: 352KB, 提交时间: 2022-06-19
#include <stdio.h>
int check(int i, int j, int x, int y) {
return (abs(i-x) + abs(j-y) == 3 && i != x && j != y) || (i == x && j == y);
}
int main() {
int n, m, x, y;
scanf("%d %d %d %d", &n, &m, &x, &y);
int i = 0;
long long **dp = (long long **)malloc(sizeof(long long *) * (n + 1));
for (i = 0; i < n + 1; i++) {
dp[i] = (long long *)malloc(sizeof(long long) * (m + 1));
}
dp[0][0] = 1;
for (i = 1; i < n + 1; i++) {
dp[i][0] = (check(i, 0, x, y) ? 0 : dp[i-1][0]);
}
for (int j = 1; j < m + 1; j++) {
dp[0][j] = (check(0, j, x, y) ? 0 : dp[0][j-1]);
}
for (i = 1; i < n + 1; i++) {
for (int j = 1; j < m + 1; j++) {
dp[i][j] = (check(i, j, x, y) ? 0 : (dp[i-1][j] + dp[i][j-1]));
}
}
printf("%lld", dp[n][m]);
for (i = 0; i < n + 1; i++) {
free(dp[i]);
}
free(dp);
return 0;
}
C 解法, 执行用时: 3ms, 内存消耗: 360KB, 提交时间: 2022-07-01
#include <stdio.h>
int fun(int x,int y,int n,int m);
int main(){
int n = 0,m = 0,x = 0,y = 0;
scanf("%d %d %d %d",&n,&m,&x,&y);
long dp[n+1][m+1];
for(int i = 0; i < n+1; i++){
for(int j = 0; j < m+1; j++){
dp[i][j] = 0;
}
}
int i = 0;
int j = 0;
if(fun(x,y,n,m)) dp[x][y] = -1;
if(fun(x+2,y+1,n,m)) dp[x+2][y+1] = -1;
if(fun(x+1,y+2,n,m)) dp[x+1][y+2] = -1;
if(fun(x-1,y+2,n,m)) dp[x-1][y+2] = -1;
if(fun(x-2,y+1,n,m)) dp[x-2][y+1] = -1;
if(fun(x-2,y-1,n,m)) dp[x-2][y-1] = -1;
if(fun(x-1,y-2,n,m)) dp[x-1][y-2] = -1;
if(fun(x+1,y-2,n,m)) dp[x+1][y-2] = -1;
if(fun(x+2,y-1,n,m)) dp[x+2][y-1] = -1;
for(i = 0; i < n+1; i++){
if(dp[i][0] == -1)
break;
dp[i][0] = 1;
}
for(j = 0; j < m+1; j++){
if(dp[0][j] == -1)
break;
dp[0][j] = 1;
}
for(i = 1; i < n+1; i++){
for(j = 1; j < m+1; j++){
if(dp[i][j] == -1 || (dp[i-1][j] == -1 && dp[i][j-1] == -1)){
continue;
}
else if(dp[i-1][j] == -1 && dp[i][j-1] != -1){
dp[i][j] = dp[i][j-1];
}
else if(dp[i-1][j] != -1 && dp[i][j-1] == -1){
dp[i][j] = dp[i-1][j];
}
else{
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
printf("%ld",dp[i-1][j-1]);
return 0;
}
int fun(int x,int y,int n,int m){
if(x >= 0 && x <= n && y >= 0 && y <= m)
return 1;
else
return 0;
}
C++ 解法, 执行用时: 3ms, 内存消耗: 392KB, 提交时间: 2022-04-07
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include <cstring>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
int x, y;
cin >> x >> y;
long long dp[n + 1][m + 1];
memset(dp, -1, sizeof(dp));//初始化为-1，这里注意下标从0开始，所以是（n+1,m+1）
dp[0][0] = 1;
if (x <= n && y <= m) {
dp[x][y] = 0;///将马所在点设为0
}
for (int i = 0; i <= n; ++i)
{
for (int j = 0; j <= m; ++j)
{
if (abs(i - x) + abs(j - y) == 3 && (i != x) && (j != y))
{
dp[i][j] = 0;//将拦马点设为0
}
}
}
for (int i = 1; i <= n; ++i)
{
if (dp[i][0]!=0)
dp[i][0] = dp[i-1][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)
{
for (int j = 1; j <= m; ++j)
{
if (dp[i][j]!=0)
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];//dp[i]不为0的点才有路径
}
}
cout << dp[n][m];
return 0;
}