[NOIP2002] 过河卒

发布于 2017-07-10  87 次阅读


一看到这题稍稍有点懵,但是仔细想想发现是大水题~~

f[i][j]表示的是从起点到(i,j)的路径数。

比较有意思的一点是,我在计算马的控制点的时候忘记控制边界了,居然AC了???

这里的正确写法应该是

int x[8]={-2,-2,-1,-1,1,1,2,2};
int y[8]={-1,1,-2,2,-2,2,1,-1};
/*
......
*/
for(i=0;i<8;i++) {
		if((y[i]+hy)>=0&&(y[i]+hy)<=20&&(x[i]+hx)>=0&&(x[i]+hx)<=20) {
			control[y[i]+hy][x[i]+hx]=1;
		}
	}

下面是我的代码:

#include<cstdio>
#include<cstring>
bool control[21][21];
int bx,by,hx,hy,f[21][21];
int main()
{
	memset(f,0,sizeof(f));
	f[0][0]=1;
	scanf("%d%d%d%d",&bx,&by,&hx,&hy);
	control[hx][hy]=1;
	control[hx-2][hy-1]=1;control[hx-2][hy+1]=1;control[hx-1][hy+2]=1;control[hx-1][hy-2]=1;
	control[hx+2][hy-1]=1;control[hx+2][hy+1]=1;control[hx+1][hy+2]=1;control[hx+1][hy-2]=1;
	for(int i=0;i<=bx;i++)
	for(int j=0;j<=by;j++)
	{
		if(i>0&&!control[i][j]) f[i][j]+=f[i-1][j];
		if(j>0&&!control[i][j]) f[i][j]+=f[i][j-1];
	}
	printf("%d\n",f[bx][by]);
	return 0;
}

 


等风来,不如追风去。