那年的埃菲尔

用户名：18839270274

访问量：19171

签　名：

我只是个蒟蒻(⊙o⊙);

等　　级
排　　名	190
经　　验	6666
参赛次数	1
文章发表	50
年　　龄	0
在职情况	学生
学　　校	郑州大学
专　　业	计算机科学与技术

　　自我简介：

欢迎加我QQ交流 540671670

TA的其他文章

连续自然数和-题解(C++代码)（简单解法）
浏览：165

诡秘的余数-题解(C++代码)
浏览：283

小O的溢出-题解(C/C++语言代码)（参考一下）
浏览：280

你可能喜欢

A+B for Input-Output Practice (VI) （C语言代码）

C语言训练-最大数问题（C语言代码）.........关于-1

马拦过河卒-题解(C/C++代码)

　　作者: 那年的埃菲尔　　　　发表时间：2020-02-12 10:54:49 浏览：428　|　评论：0　

原题链接：马拦过河卒

#### 解题思路：
用g[x][y]记录棋盘的状态，每个位置默认状态为0，卒可以经过；马所在位置以及马可达的8个位置状态为1，不允许卒经过。用f[i][j]记录从点(0,0)到点(i,j)的路径条数，根据卒行走的规则，f[0][0]为1，当j==0，棋盘数组第一列f[i][0]=f[i-1][0]，当i==0，棋盘数组第一行f[0][j]=f[0][j-1]；当i属于[1,n]、j属于[1,m]，f[i][j]=f[i-1][j]+f[i][j-1]。

#### 参考代码：
```cpp
#include<iostream>
#include<iomanip>
using namespace std;

int main()
{
	int n , m , x , y ;
	int g[20][20] = {0};
	int f[20][20] = {0};
	int dx[8] = {-2 ,-1 ,1 ,2 ,2 ,1 ,-1 ,-2}; //马可以走到的点 假设以0为马所在点 
    int dy[8] = {1 ,2 ,2 ,1 ,-1 ,-2 ,-2 ,-1};
    	cin >> n >> m >> x >> y;
    g[x][y] = 1;		//马所在的位置状态为1
    
	for(int i = 0 ; i < 8 ; i++)
    	if(x + dx[i] >= 0 && x + dx[i] <= n && y + dy[i] >= 0 && y + dy[i] <= m)
    		g[x + dx[i]][y + dy[i]] = 1;	//马可达的8个位置状态为1
    
	f[0][0] = 1;		//初始化可达原点的路径数
    for(int i = 1 ; i <= n ; i++)	//初始化第一列的路径数
    	if(g[i][0] == 0)
			f[i][0] = f[i-1][0];
	
	for(int j = 1 ; j <= m ; j++)	//初始化第一行的路径数
		if(g[0][j] == 0)
			f[0][j] = f[0][j-1];
	
	for(int i = 1 ; i <= n ; i++)
		for(int j = 1 ; j <= m ; j++)
			if(g[i][j] == 0)
				f[i][j] = f[i-1][j] + f[i][j-1];	//若可达，从两个可能方向继承前一步的路径数
	cout << f[n][m] << endl;
	return 0;
}
```

以下是C版本解法：
```c
#include<stdio.h>
int main()
{
	int i ,j ,n ,m ,x ,y;
	int g[20][20] = {0};
	int f[20][20] = {0};
    int dx[8] = {-2 ,-1 ,1 ,2 ,2 ,1 ,-1 ,-2};
    int dy[8] = {1 ,2 ,2 ,1 ,-1 ,-2 ,-2 ,-1};
    	scanf("%d%d%d%d", &n, &m, &x, &y);
    g[x][y] = 1;
    
	for(i = 0 ; i < 8 ; i++)
    	if(x + dx[i] >= 0 && x + dx[i] <= n && y + dy[i] >= 0 && y + dy[i] <= m)
    		g[x + dx[i]][y + dy[i]] = 1;	
    
	f[0][0] = 1;
    for(i = 1 ; i <= n ; i++)
    	if(g[i][0] == 0)
			f[i][0] = f[i-1][0];
	
	for(j = 1 ; j <= m ; j++)
		if(g[0][j] == 0)
			f[0][j] = f[0][j-1];
	
	for(i = 1 ; i <= n ; i++)
		for(j = 1 ; j <= m ; j++)
			if(g[i][j] == 0)
				f[i][j] = f[i-1][j] + f[i][j-1];
	printf("%d\n" , f[n][m]);
	return 0;
 } 
```

0.0分

2 人评分

新上线《蓝桥杯辅导》课程，近五年的蓝桥杯省赛与国赛真题都有，从读题开始理解题意、梳理思路、实现代码再提交评测全过程，可有效提升获奖比例甚至进国赛！课程介绍、试听请猛击这里

那年的埃菲尔

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C二级辅导-温度转换（C语言代码）

A+B for Input-Output Practice (VI) （C语言代码）

C语言训练-最大数问题（C语言代码）.........关于-1

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

马拦过河卒-题解(C/C++代码)

评论区

精彩推荐

printf基础练习2 （C语言代码）

简单的a+b （C语言代码）

妹子杀手的故事（C语言代码）

输出正反三角形（C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言训练-亲密数（C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

图形输出（C语言代码）

那年的埃菲尔

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C二级辅导-温度转换 （C语言代码）

A+B for Input-Output Practice (VI) （C语言代码）

C语言训练-最大数问题 （C语言代码）.........关于-1

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

马拦过河卒-题解(C/C++代码)

评论区

精彩推荐

printf基础练习2 （C语言代码）

简单的a+b （C语言代码）

妹子杀手的故事 （C语言代码）

输出正反三角形 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言训练-亲密数 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

图形输出 （C语言代码）

C二级辅导-温度转换（C语言代码）

C语言训练-最大数问题（C语言代码）.........关于-1

　　评论区

妹子杀手的故事（C语言代码）

输出正反三角形（C语言代码）

C语言训练-亲密数（C语言代码）

图形输出（C语言代码）