题目

题目链接

思路

过河卒问题
因为小卒只能向右或者向下走，那么可到达某一点的路径即为左面点和上面点路径之和，	
其中一个有9个被马控制的点
我们利用dp数组，将马能控制的地方都设为-1，其余地方设为0 

我的代码

我的代码有点麻烦（就是在那个判断被?控制住的点的时候）
因此后面填充dp的时候也有点麻烦了

/*
过河卒问题
因为小卒只能向右或者向下走，那么可到达某一点的路径即为左面点和上面点路径之和，其中一个有9个被马控制的点
我们利用dp数组，将马能控制的地方都设为-1，其余地方设为0 
 
*/

#include<iostream>
using namespace std;
long long dp[22][22]={0};
long long n,m,a,b;
int main(){
	cin>>n>>m>>a>>b;//(n,m)为B点坐标，(a,b)为马的坐标 
	//这个方法可能很笨(就是将不能走的9个点全部标记出来)：
	//所有点的范围都应该横坐标在[0,n]纵坐标在[0,m] 
	if(a>=0&&a<=n&&b>=0&&b<=m)
		dp[a][b]=-1;
	if(a+1>=0&&a+1<=n&&b+2>=0&&b+2<=m)
		dp[a+1][b+2]=-1;
	if(a+2>=0&&a+2<=n&&b+1>=0&&b+1<=m)
		dp[a+2][b+1]=-1;
	if(a+2>=0&&a+2<=n&&b-1>=0&&b-1<=m)
		dp[a+2][b-1]=-1;
	if(a+1>=0&&a+1<=n&&b-2>=0&&b-2<=m)
		dp[a+1][b-2]=-1;
	if(a-1>=0&&a-1<=n&&b-2>=0&&b-2<=m)
		dp[a-1][b-2]=-1;
	if(a-2>=0&&a-2<=n&&b-1>=0&&b-1<=m)
		dp[a-2][b-1]=-1;
	if(a-2>=0&&a-2<=n&&b+1>=0&&b+1<=m)
		dp[a-2][b+1]=-1;
	if(a-1>=0&&a-1<=n&&b+2>=0&&b+2<=m)
		dp[a-1][b+2]=-1;
	//呜呜~~我so憨 
	/*
		接下来要做的，就是把我们的dp数组补充好 
		首先需要初始化dp[i][0]和dp[0][i]这两条边 
	*/ 
	for(int i=0;i<=n;i++){//初始化边界列 
		if(dp[i][0]!=-1)
			dp[i][0]=1;
		else
			break;//这里break是因为一旦某个位置被控制了，由于是边界，后面的点都无法到达了 
	}
	for(int i=0;i<=m;i++){//初始化边界行 
		if(dp[0][i]!=-1)
			dp[0][i]=1;
		else
			break;
	}
	//边界初始化成功 
	
	//开始把dp数组给弄了 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(dp[i][j]==-1){
				continue;
			}
			if(dp[i-1][j]!=-1&&dp[i][j-1]!=-1){
				dp[i][j]=dp[i-1][j]+dp[i][j-1];
			}
			else{
				if(dp[i-1][j]==-1&&dp[i][j-1]==-1)
					dp[i][j]=0;
				if(dp[i-1][j]==-1&&dp[i][j-1]!=-1)
					dp[i][j]=dp[i][j-1];
				if(dp[i-1][j]!=-1&&dp[i][j-1]==-1)
					dp[i][j]=dp[i-1][j];
			}
		}
	}
	cout<<dp[n][m];
	return 0;
}

代码优化

这个是别人的代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;

const int fx[] = {0, -2, -1, 1, 2, 2, 1, -1, -2};
const int fy[] = {0, 1, 2, 2, 1, -1, -2, -2, -1};
//马可以走到的位置

int bx, by, mx, my;
ll f[40][40];
bool s[40][40]; //判断这个点有没有马拦住
int main(){
    scanf("%d%d%d%d", &bx, &by, &mx, &my);
    bx += 2; by += 2; mx += 2; my += 2;
    //坐标+2以防越界
    f[2][1] = 1;//初始化
    s[mx][my] = 1;//标记马的位置
    for(int i = 1; i <= 8; i++) s[mx + fx[i]][my + fy[i]] = 1;
    for(int i = 2; i <= bx; i++){
        for(int j = 2; j <= by; j++){
            if(s[i][j]) continue; // 如果被马拦住就直接跳过
            f[i][j] = f[i - 1][j] + f[i][j - 1];
            //状态转移方程
        }
    }
    printf("%lld\n", f[bx][by]);
    return 0;
} 

有几个相对我的代码简单的点：

• const int fx[] = {0, -2, -1, 1, 2, 2, 1, -1, -2};
  const int fy[] = {0, 1, 2, 2, 1, -1, -2, -2, -1};
  然后for(int i = 1; i <= 8; i++) s[mx + fx[i]][my + fy[i]] = 1;
  这样的话就不要写那么多赋值语句了，不过都得执行8次

• bx += 2; by += 2; mx += 2; my += 2;
  这一点也很好，就是相当于把棋盘扩大了，但是呢，对于那些被被占领的点所出现的越界情况就不要考虑了，因为那些点都被标注了，而且不会出现在真正有用的棋盘区域内

• 另外那个bool值的数据使用了也就方便一些