题意

哈理工2016级新生程序设计全国邀请赛A题

http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=2293

(0,0)走到(n,m)有多少种走法，每次向下或向右，其中(x,y)和(x,y)走日字能到的点不能走。

1<n,m<20

题解

递推，f[i][j]=f[i-1][j]+f[i][j-1]

边界：f[0][0]=1。

代码

#include<cstdio>

#include<cstring>

int n,m,x,y;

long long f[25][25]={1};//注意开long long

bool no[25][25];

int dx[9]={-2,-2,-1,-1,1,1,2,2},

    dy[9]={1,-1,2,-2,2,-2,1,-1};

int main(){

    int t;

    scanf("%d",&t);

    while(t--){

        scanf("%d%d%d%d",&n,&m,&x,&y);

        memset(no,0,sizeof no);

        no[x][y]=1;

        for(int i=0;i<8;i++)

            if(x+dx[i]>=0&&y+dy[i]>=0)//注意判断范围

                no[x+dx[i]][y+dy[i]]=1;//代表不能走

        for(int i=0;i<=n;i++)

        for(int j=0;j<=m;j++)

            if(!no[i][j]){//可行的点

                if(i||j)//不能更新f[0][0],因为它是我们的边界值

                    f[i][j]=(i?f[i-1][j]:0)+(j?f[i][j-1]:0);

            }else

                f[i][j]=0;

        printf("%lld\n",f[n][m]);

    }

}