被玩坏了的题——马的遍历

快来打我* 2021-12-16 03:57 256阅读 0赞

# 马的疑惑 #

今天在洛谷上看到这道题，想起了夕阳下的棋盘。于是我尝试去做了做，二话不说看题。

## [一扇穿越到洛谷的门：][Link 1] ##

## 思考： ##

如图，是我们象棋中马的走位走的方向。

![1716525-20190617213016286-157735342.jpg][]

首先看到这道题，我们要确定马能跳的方位，我们设马的坐标为（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://www.cnblogs.com/YYCether666/p/11042387.html

[Link 1]: https://www.luogu.org/problemnew/show/P1443
[1716525-20190617213016286-157735342.jpg]: /images/20211214/14345c04bec6437bba403bd652fca6fe.png