大家好，欢迎来到IT知识分享网。
马的疑惑
今天在洛谷上看到这道题，想起了夕阳下的棋盘。于是我尝试去做了做，二话不说看题。
一扇穿越到洛谷的门：
思考：
如图，是我们象棋中马的走位走的方向。
首先看到这道题，我们要确定马能跳的方位，我们设马的坐标为（x，x）。很容易知道马可以跳到（x+1)(y+2),(x+2)(y+1),(x+2)(y-1),(x+1)(y-2),(x-1)(y-2),
(x-2)(y-1),(x-2)(y+1),(x-1)(y+2).总共八个搜索方向。由于是最短路径问题，所以自然容易想到宽搜（BFS）然而，由于你们亲爱的博主太LJ以至于他连宽搜的
不会。博主成功自闭。。。好的，经过一番思想斗争。我决定要学好宽搜用深搜来做。也就是八个if，没什么大不了。
然后前提是马跳的位置不能超出棋盘，还有如果已经有了最优解就没必要在搜了。
代码：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,m,madex,madey,a[601][601]; void dfs(int,int,int); int main() { cin>>n>>m>>madex>>madey; memset(a,-1,sizeof(a)); dfs(madex,madey,0); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) printf("%-5d",a[i][j]); printf("\n"); } return 0; } void dfs(int x,int y,int step) { a[x][y]=step; if(y+1<=m&&x+2<=n&&(a[x+2][y+1]==-1||a[x+2][y+1]>step)) dfs(x+2,y+1,step+1); if(y-1>0&&x+2<=n&&(a[x+2][y-1]==-1||a[x+2][y-1]>step)) dfs(x+2,y-1,step+1); if(y+1<=m&&x-2>=0&&(a[x-2][y+1]==-1||a[x-2][y+1]>step)) dfs(x-2,y+1,step+1); if(x-2>0&&y-1>0&&(a[x-2][y-1]==-1||a[x-2][y-1]>step)) dfs(x-2,y-1,step+1); if(x+1<=n&&y-2>0&&(a[x+1][y-2]==-1||a[x+1][y-2]>step)) dfs(x+1,y-2,step+1); if(x+1<=n&&y+2<=m&&(a[x+1][y+2]==-1||a[x+1][y+2]>step)) dfs(x+1,y+2,step+1); if(x-1>0&&y-2>0&&(a[x-1][y-2]==-1||a[x-1][y-2]>step) ) dfs(x-1,y-2,step+1); if(x-1>0&&y+2<=m&&(a[x-1][y+2]==-1||a[x-1][y+2]>step)) dfs(x-1,y+2,step+1); }
然后这道题就成功被我玩坏了，哈哈哈
上洛谷一看三个AC，七个TLE。我的内心是崩溃的。呜呜呜！
好了，我太蒟蒻了，各位大佬们取用宽搜吧！
宽搜真的很重要！
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/33444.html
