本文主要是介绍逃亡路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
由于不能与Garfield和睦相处，Odie决定逃亡。不幸的他逃到了一个矩形湖泊。湖泊的长为N，宽为M，初始时Odie位于位置（1，1）。Garfield想要知道可怜的Odie有到达位置（N，M）的最短路径条数（不能跳出湖泊边界）。另外，神奇的Odie移动方式类似国际象棋的骑士。
输入
两个整数N和M，表示湖泊的长和宽。
输出
一个整数，表示最短路径的条数（模9901输出即可）。
输入样例
3 3
输出样例
2
说明
对于50%的数据，N ≤ 5，
对于100%的数据，N ≤ 100。
.
.
.
.
.
.
分析
注意题目要求的是最短的路径的条数
直接bfs即可
.
.
.
.
.
程序(70分的dfs)：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;int n,m,minn=2147483647,ans=0;
bool f[110][110];
int dx[8]={-2,-2,-1,-1,1,1,2,2};
int dy[8]={1,-1,2,-2,2,-2,-1,1};void dfs(int x,int y,int w)
{if (w>minn) return;if (x==n&&y==m){if (w<minn){minn=w;ans=0;}ans=(ans+1)%9901;return;}for (int i=0;i<=7;i++)if (f[x+dx[i]][y+dy[i]]==false&&x+dx[i]>=1&&x+dx[i]<=n&&y+dy[i]>=1&&y+dy[i]<=m){f[x+dx[i]][y+dy[i]]=true;dfs(x+dx[i],y+dy[i],w+1);f[x+dx[i]][y+dy[i]]=false;}
}int main()
{scanf("%d%d",&n,&m);memset(f,false,sizeof(f));f[1][1]=true;dfs(1,1,0);printf("%d",ans%9901);return 0;
}
.
.
.
.
.
.
程序(100分的bfs)：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;int n,m,a[110][110],d[110][110];
bool f[110][110];
int dx[8]={-2,-2,-1,-1,1,1,2,2};
int dy[8]={1,-1,2,-2,2,-2,-1,1};
queue<int>qx,qy;void bfs()
{qx.push(1);qy.push(1);while(!qx.empty()){int x=qx.front();qx.pop();int y=qy.front();qy.pop();f[x][y]=false;for (int i=0;i<=7;i++){int ax=x+dx[i],ay=y+dy[i];if (ax<1||ay<1||ax>n||ay>m) continue;if (d[ax][ay]>d[x][y]+1){d[ax][ay]=d[x][y]+1;if (!f[ax][ay]){f[ax][ay]=1;qx.push(ax);qy.push(ay);}a[ax][ay]=a[x][y];} elseif (d[ax][ay]==d[x][y]+1) a[ax][ay]=(a[x][y]+a[ax][ay])%9901;}}
}int main()
{scanf("%d%d",&n,&m);memset(f,false,sizeof(f));f[1][1]=true;memset(d,0X3f,sizeof(d));d[1][1]=0;a[1][1]=1;bfs();printf("%d",a[n][m]);return 0;
}
这篇关于逃亡路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
