26.篮球练习

Description

小徐酷爱打篮球，在小学期的前两周半都在练习篮球。今天，小徐想要练习如何突破。
练习场地可由如下所示的网格图表示，图中的位置可用坐标表示。
其中A点(0,0)为小徐的起始位置，B点(n,m)为小徐想要到达的位置。
一起训练的还有场上的防守队员小彩，其位于C点。已知小徐行动时只能向右或向下前进，且当小徐相对于小彩的位置为Pi(i = 1,2…8)时，小徐会被抢断(注：在C点时同样会被抢断）。

注意,Pi坐标是会随C位置的变化而变化的，但相对位置是固定的.
现在要求你计算小徐从A点到达B点且不被抢断的路径条数。假设小彩的位置是固定不动的，并不是小徐走一步小彩走一步。

Input

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

Output

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

Hint

对于全部的数据，1≤n,m≤20，0≤ C点的横纵坐标 ≤20。

思路

动态规划的简单练习。最需要注意的是数据太大，需要用到long long
long long dp[i][j]，先初始化dp[0][j]和dp[i][0]，能到达就是1，到不了就是0。然后对整个dp[i][j]操作，如果该点不会被抢断，dp[i][j]=dp[i-1][j]+dp[i][j-1]，到达该点的路径数为其上和左路径数之和。最后输出dp[n][m]即可。还有是除了 $p_i$ 8个点，c点也不能通过.

代码

#include<stdio.h>
#include<stdlib.h>
#define isOK(i,j) (abs(p-i)+abs(q-j)==3 && p-i && q-j || abs(p-i)+abs(q-j)==0)?0:1
int main()
{
	int n,m,p,q,i=0,j=0;
	long long dp[21][21]={0};
	//B点(n,m) C点(p,q)
	scanf("%d %d %d %d",&n,&m,&p,&q);
	
	dp[0][0]=1;
	for(i=1;i<=n;i++){
		if(isOK(i,0))	dp[i][0]=dp[i-1][0];
		else	dp[i][0]=0;
	}	
	for(j=1;j<=m;j++){
		if(isOK(0,j))	dp[0][j]=dp[0][j-1];
		else	dp[0][j]=0;
	}	
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			if(isOK(i,j))	dp[i][j]=dp[i-1][j]+dp[i][j-1];
			else	dp[i][j]=0;
		}
	}
	
	printf("%lld\n",dp[n][m]);
}