P1002 过河卒(洛谷）

比眉伴天荒 2023-05-22 02:29 1阅读 0赞

## **题目描述** ##

棋盘上 A 点有一个过河卒，需要走到目标B 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示，A 点 (0, 0)、B 点 (n,m)，同样马的位置坐标是需要给出的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY1Mjc2NQ_size_16_color_FFFFFF_t_70]

现在要求你计算出卒从 A 点能够到达B 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

## 输入格式 ##

一行四个正整数，分别表示B 点坐标和马的坐标。

## 输出格式 ##

一个整数，表示所有的路径条数。

## 输入输出样例 ##

**输入** \#1  
6 6 3 3

**输出**

1  
6  
**说明/提示**  
对于 100% 的数据1≤n,m≤20，0≤ 马的坐标≤20。

## 解题思路：如果用深搜的话，那么当N，M到达了15之后就会超时。因此我们选择动态规划–递推。只要找出状态转移方程即可，那么状态转移方程如何寻找？设sum\[i\]\[j\]为从0，0走到i，j的路径数，通过观察和证明我们知道sum\[i\]\[j\]=sum\[i-1\]\[j\]+sum\[i\]\[j-1\]，这个就是我们要的状态转移方程了。根据这个就可以愉快地进行递推了。 ##

**注意点**：\*\*\*\*被马阻碍的点要进行标记，该点的sum=0;同时第一行和第一列也要特别注意，如果该列或行中出现了第一个马阻碍点，那么后续的点都是走不了的，即也是马阻碍点。在第一行第一列中马阻碍点的sum都是0，其余非阻碍点的sum为1.**还要注意的是sum\[n\]\[m\]可能会很大，要开long long.**

#include<iostream>
    using namespace std;
    long long product[25][25];
    int v[25][25];//标记是否是被马阻挡的点 
    int n,m,x,y;
    void horse()//对不可通行的行标记为一 
    { 
    	v[x][y]=1;
    	for(int i=x-2;i<=x+2;i=i+4)
    	for(int j=y-1;j<=y+1;j=j+2)
    	if(i>=0&&i<=n&&j>=0&&j<=m)
    	v[i][j]=1;
    	for(int i=x-1;i<=x+1;i=i+2)
    	for(int j=y-2;j<=y+2;j=j+4)
    	if(i>=0&&i<=n&&j>=0&&j<=m)
    	v[i][j]=1;
    }
    int main()
    { 
    	cin>>n>>m>>x>>y;//输入终点的坐标(行和列）和马的坐标
    	horse();
    	for(int i=0;i<=n;i++)//初始化第一列
    	if(v[i][0]==1)//特判 马阻碍点 出现后，之后的点都是走不了的 
    	break;
    	else
    	product[i][0]=1;
    	for(int j=0;j<=m;j++)//初始化第一行
    	if(v[0][j]==1) //特判 马阻碍点 
    	break;
    	else
    	product[0][j]=1;
    	for(int i=1;i<=n;i++)
    	for(int j=1;j<=m;j++)
    	{ 
    	    if(v[i][j]==1)//特判 马阻碍点 
    		product[i][j]=0;
    		else
    		product[i][j]=product[i][j-1]+product[i-1][j];
    		
    	}
    	cout<<product[n][m];
    	return 0;
     }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY1Mjc2NQ_size_16_color_FFFFFF_t_70]: /images/20230521/11f658374f5d4268a00b603bdef810c7.png