[noip2002 popularization group] cross the river pawn

Go through all the hardships , I finally $AC$ La ！

[NOIP2002 Popularization group ] River crossing pawn

Title Description

On the chessboard $A$ There is a river crossing pawn , Need to get to the goal $B$ spot . The rules of pawn walking ： You can go down 、 Or to the right . At the same time on the chessboard $C$
There's a horse on the other side , The point where the horse is located and all the points that can be reached in one step of jumping are called the control points of the opposing horse . So it's called “ A pawn crossing the river ”.

The chessboard is represented by coordinates ,$A$ spot $(0,0)$、$B$ spot $(n,m)$, The same coordinates of the horse's position need to be given .

Now I ask you to calculate the number of soldiers from $A$ Point can reach $B$ The number of paths of points , Suppose the horse's position is fixed , It's not a step by step .

Input format

Four positive integers in a row , respectively $B$ Point coordinates and horse coordinates .

Output format

An integer , Indicates the number of paths .

Examples #1

The sample input #1

6 6 3 3

Sample output #1

6

Tips

about $100\%$ The data of ,$1\le n,m\le 20$,$0\le$ Horse coordinates $\le 20$.

【 Title source 】

NOIP 2002 Question 4 of the popularization group

Let's look at this problem together , yes NOIP The last question of （ For my kind of konjaku , It's already very difficult ）, The algorithmic label given by Luogu official is dynamic programming ！

Let's think about it , Simplify if you can .

Before that , Let's think about one thing first , For example, this grid , We from $S$ Go to the $E$, How many different ways to walk ？

It's simple , Elementary school mathematics filling method .

alike , Let's think about , Simulate their position , Find the recurrence relation ：

Obvious ,$a(i,j)=a(i-1,j)+a(i,j-1)$ Is the relation of this question , It is also the relation of this big problem .

Now? , Let's think about this problem .
alike , We can be sure , Show the coordinates where the horse can move , Then mark 0.
（ Pay attention to this question $longlong$ Ha , Otherwise it's out of range ）

	//  input data 
	long long a[100][100]={
    };
	int n,m,x,y;
	cin>>n>>m>>x>>y;
	for(int i=0;i<=n;i++){
    
		for(int j=0;j<=m;j++){
    
			a[i][j]=1;
		}
	}
	//  Represents the coordinates of the horse 
	a[x][y]=0;
	if(x-2>=0&&y-1>=0) a[x-2][y-1]=0;
	if(x-2>=0&&y+1<=m) a[x-2][y+1]=0;
	if(x-1>=0&&y-2>=0) a[x-1][y-2]=0;
	if(x-1>=0&&y+2<=m) a[x-1][y+2]=0;
	if(x+1<=n&&y-2>=0) a[x+1][y-2]=0;
	if(x+2<=n&&y-1>=0) a[x+2][y-1]=0;
	if(x+2<=n&&y+1<=m) a[x+2][y+1]=0;
	if(x+1<=n&&y+2<=m) a[x+1][y+2]=0;

Judge whether you crossed the line , If you cross the line , You can't move .

Recursion of the core , Here it is ：

$i=0$ It's the first line , Except for control points , Only from the left ,$a(i,j)=$ The value on the left side
$j=0$ It's the first column , Except for control points , Only from above ,$a(i,j)=$ The value above
The rest , Except for control points , Sum according to the previous relation $a(i,j)=a(i-1,j)+a(i,j-1)$

	for(int i=0;i<=n;i++){
    
		for(int j=0;j<=m;j++){
    
			if(i==0&&j==0) continue;
			if(a[i][j]==0) continue;
			if(i==0) a[i][j]=a[i][j-1];
			else if(j==0) a[i][j]=a[i-1][j];
			else a[i][j]=a[i-1][j]+a[i][j-1];
		}
	}

Finally, simply , The output is over .

	cout<<a[n][m];
	/* //  Output the number of each position  for(int i=0;i<=n;i++){ for(int j=0;j<=m;j++){ cout<<a[i][j]<<" "; } cout<<endl; } */

A complete map ：

1 1 1 1 1 1 1
1 2 0 1 0 1 2
1 0 0 1 1 0 2
1 1 1 0 1 1 3
1 0 1 1 2 0 3
1 1 0 1 0 0 3
1 2 2 3 3 3 6

The complete code is as follows ：

// Author:PanDaoxi
#include <iostream>
using namespace std;
int main(){
    
	long long a[100][100]={
    };
	int n,m,x,y;
	cin>>n>>m>>x>>y;
	for(int i=0;i<=n;i++){
    
		for(int j=0;j<=m;j++){
    
			a[i][j]=1;
		}
	}
	a[x][y]=0;
	if(x-2>=0&&y-1>=0) a[x-2][y-1]=0;
	if(x-2>=0&&y+1<=m) a[x-2][y+1]=0;
	if(x-1>=0&&y-2>=0) a[x-1][y-2]=0;
	if(x-1>=0&&y+2<=m) a[x-1][y+2]=0;
	if(x+1<=n&&y-2>=0) a[x+1][y-2]=0;
	if(x+2<=n&&y-1>=0) a[x+2][y-1]=0;
	if(x+2<=n&&y+1<=m) a[x+2][y+1]=0;
	if(x+1<=n&&y+2<=m) a[x+1][y+2]=0;
	for(int i=0;i<=n;i++){
    
		for(int j=0;j<=m;j++){
    
			if(i==0&&j==0) continue;
			if(a[i][j]==0) continue;
			if(i==0) a[i][j]=a[i][j-1];
			else if(j==0) a[i][j]=a[i-1][j];
			else a[i][j]=a[i-1][j]+a[i][j-1];
		}
	}
	cout<<a[n][m];
	/* for(int i=0;i<=n;i++){ for(int j=0;j<=m;j++){ cout<<a[i][j]<<" "; } cout<<endl; } */
	return 0;
}

Luogu $AC$ .