首页 > 代码库 > NOIP200204过河卒(C++)

NOIP200204过河卒(C++)

#include<stdio.h>
#include<string.h>

int n,m,X,Y;
int map[25][25];
long long dp[25][25];

int move[8][2]={{-1,2},{-2,1},{1,2},{2,1},{-1,-2},{-2,-1},{1,-2},{2,-1}};

int inarea(int x,int y)
{
return x>=0 && y>=0 && x<n && y<m;
}

int main()
{
scanf("%d%d%d%d",&n,&m,&X,&Y); 
memset(map, 0, sizeof(map)); 
memset(dp, 0, sizeof(dp));
n+=1;
m+=1;

if (inarea(X,Y)) map[X][Y]=1;
for (int i=0; i<8; i++)
if (inarea(X+move[i][0],Y+move[i][1]))
map[X+move[i][0]][Y+move[i][1]]=1;

dp[0][0]=1; 
for (int i=1; i<n; i++) {
if(!map[i][0])dp[i][0]=dp[i-1][0];
else dp[i][0]=0;
}
for (int i=1; i<m; i++) {
if(!map[0][i])dp[0][i]=dp[0][i-1];
else dp[0][i]=0;
}

for (int i=1; i<n; i++)
for (int j=1; j<m; j++) {
if (!map[i][j])
dp[i][j]=dp[i-1][j]+dp[i][j-1];
else dp[i][j]=0;
}

printf("%lld\n",dp[n-1][m-1]);
}

NOIP200204过河卒(C++)