HUST软件与微电子学院第八届程序设计竞赛-小乐乐下象棋

这题其实很简单，我们可以用一个bfs搜索出所有的，小于k步的，到不同点不同步数的方案数。

我们首先初始化，走到（0,0）点的时候，我们把步数设置为0，但是方法数设置为1，这是因为我们走零步，到一个点，确实有一种方法。

然后就是bfs，当步数等于k的时候，我们就跳过这点，因为题目中要求是等于k步，即使你搜了大于k步的方案数，我们也用不着。

越界判断之后，我么先加上从别的点到达下一个点的方案数，取模之后，我们再判断这点我们是否在current.step+1的基础上走过我们准备走的下一点。

这也就是说，我们是否曾经已经用相通的步数走过这点，第一次肯定是没有走过的，但是如果之后也走出了这种情况，我们就continue了，我们已经把这个点放进去过队列了，我们就不再重复搜索。

#include <iostream>

#include <cstring>

#include <queue>

using namespace std;

const int mod=1e9+7;

const int maxn=205;

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

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

struct Status

{

    int x,y;

    int Step;

    Status(int a,int b,int c):x(a),y(b),Step(c){}

};

int n,m,k;

int visited[maxn][maxn][maxn];

int dp[maxn][maxn][maxn];

queue <Status> q;

void bfs()

{

    while (!q.empty()) {

        Status cur=q.front();

        q.pop();

        if (cur.Step==k)

            continue;

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

            int dx=cur.x+Dx[i];

            int dy=cur.y+Dy[i];

            if (dx<0||dy<0||dx>=n||dy>=m)

                continue;

            dp[dx][dy][cur.Step+1]+=dp[cur.x][cur.y][cur.Step];

            dp[dx][dy][cur.Step+1]%=mod;

            if (visited[dx][dy][cur.Step+1])

                continue;

            q.push(Status(dx,dy,cur.Step+1));

            visited[dx][dy][cur.Step+1]=1;

        }

    }

}

int main()

{

    while (~scanf("%d%d%d,",&n,&m,&k)) {

        memset(visited,0,sizeof(visited));

        memset(dp,0,sizeof(dp));

        q.push(Status(0,0,0));

        visited[0][0][0]=1;

        dp[0][0][0]=1;

        bfs();

        cout<<dp[n-1][m-1][k]<<endl;;

    }

    return 0;

}