题目

题目描述

由于不能与Garfield和睦相处，Odie决定逃亡。不幸的他逃到了一个矩形湖泊。湖泊的长为N，宽为M，初始时Odie位于位置（1，1）。Garfield想要知道可怜的Odie有到达位置（N，M）的最短路径条数（不能跳出湖泊边界）。另外，神奇的Odie移动方式类似国际象棋的骑士。
 

输入

两个整数N和M，表示湖泊的长和宽。

输出

一个整数，表示最短路径的条数（模9901输出即可）。

输入样例复制

3 3

输出样例复制

2

说明

对于50%的数据，N ≤ 5，
对于100%的数据，N ≤ 100。

分析

直接最短路？但记录路径要开数组

代码

 1 #include<iostream> 2 #include<queue> 3 #include<cstring> 4 using namespace std; 5 int n,m; 6 int vis[1001][1001],dis[1001][1001],ans[1001][1001]; 7 int fx[9][2]={{0,0},{1,2},{2,1},{-1,-2},{-2,-1},{1,-2},{-1,2},{-2,1},{2,-1}}; 8 void bfs() 9 {10     memset(dis,0x3f,sizeof(dis));11     queue<int> q;12     q.push(1); q.push(1); vis[1][1]=1; dis[1][1]=0; ans[1][1]=1;13     while(!q.empty())14     {15         int x=q.front(); q.pop();16         int y=q.front(); q.pop();17         vis[x][y]=0;18         for (int i=1;i<=8;i++)19         {20             int ax=x+fx[i][0],ay=y+fx[i][1];21             if (ax<1||ay<1||ax>n||ay>m) continue;22             if (dis[ax][ay]>dis[x][y]+1)23             {24                 dis[ax][ay]=dis[x][y]+1;25                 if (!vis[ax][ay])26                 {27                    vis[ax][ay]=1;28                    q.push(ax); q.push(ay);29                 }30                 ans[ax][ay]=ans[x][y];31             }32             else if (dis[ax][ay]==dis[x][y]+1)33               ans[ax][ay]=(ans[x][y]+ans[ax][ay])%9901;34         }35     }36 }37 int main ()38 {39     cin>>n>>m;40     bfs();41     cout<<ans[n][m];42 }