ACM 马拦过河卒(动态规划)

时间:2021-10-07 03:25:27

ACM 马拦过河卒(动态规划)

解题思路:

用一个二维数组a[i][j]标记 马的位置和马的跳点(统称控制点)该位置=1;

再用一个二维数组f[i][j]表示行进的位置,如果前一行的当前列不是马的控制点,或者前一列的当前行不是马的控制点,则说明是可走的,

f[i][j]+=f[i-1][j];  f[i][j]+=f[i][j-1];

最后输出 f[目标x][目标y]

AC code:

 #include<bits/stdc++.h>
using namespace std;
int a[][],f[][];
int x[]= {,,,,-,-,-,-};
int y[]= {,,-,-,-,-,,};
int main()
{
int x1,y1,x2,y2;
while(scanf("%d%d%d%d",&x1,&y1,&x2,&y2)!=EOF)
{
a[x2][y2]=;
for(int i=; i<=; i++)
if(x2+x[i]<=x1&&y2+y[i]<=y1)
a[x2+x[i]][y2+y[i]]=;
f[][]=;
for(int i=; i<=x1; i++)
for(int j=; j<=y1; j++)
{
if(i>&&!a[i-][j])
f[i][j]+=f[i-][j];
if(j>&&!a[i][j-])
f[i][j]+=f[i][j-];
}
printf("%d\n",f[x1][y1]);
}
return ;
}