【NYOJ58】最小步数

绝地灬酷狼 2022-09-24 08:30 217阅读 0赞

![这里写图片描述][20160728112408449]  
![这里写图片描述][20160728112417725]

第一道DFS（深度搜索）题目  
DFS概念：从分支的最底层开始搜索，层级依次往上，再找本层级的下一级分支。啊是不是太抽象，理解了这道题及代码，基本上就大概理解深搜了，就是这么神奇。  
再说本题，你在迷宫里移动，遇0能过，遇1打住。  
你只有四个方向可以选择，如果那个方向上的下一个数字为0，那么你可以过去，此时通过的总步数加1，上一个节点标记为1表示来过不能重复走。再以当前节点为基准，不断调用自身递归遍历所有的情况。  
DFS属于暴力耗时的，因为他要便利所有的情况，据说还能根据题目要求进行剪枝，不过我还没遇到那类题目，遇到后再分享给大家。

DFS

#include<math.h>
    #include<stdio.h>
    #include<algorithm>
    #include<climits>
    #include<queue>
    #define M 10000
    using namespace std;
    int x,y,ex,ey,ans;
    int map[9][9]= {
        1,1,1,1,1,1,1,1,1,
        1,0,0,1,0,0,1,0,1,
        1,0,0,1,1,0,0,0,1,
        1,0,1,0,1,1,0,1,1,
        1,0,0,0,0,1,0,0,1,
        1,1,0,1,0,1,0,0,1,
        1,1,0,1,0,1,0,0,1,
        1,1,0,1,0,0,0,0,1,
        1,1,1,1,1,1,1,1,1
    };
    int px[4]= {-1,1,0,0};//表示上下左右移动后，x坐标变化。
    int py[4]= {
       0,0,-1,1};//同上，y坐标对应的变化。
    void f(int x,int y,int c) {
       //深搜函数
        if(x==ex&&y==ey) { //判断如果到达最后节点，如果经过的步数
            if(c<ans)//c更少，就更新ans为这个更小的值。
                ans=c;
        } else {
            for(int l=0; l<4; l++) {
       //每个节点可能的四种移动情况
                int nx=x+px[l];
                int ny=y+py[l];
                if(c+1<ans&&map[nx][ny]==0) {
       //判断能否继续走
                    map[nx][ny]=1;//上层标记，防止重复
                    f(nx,ny,c+1);//对此层级以下情况递归遍历
                    map[nx][ny]=0;//回溯为原值0
                }
            }
        }
    }
    int main() {
        int T;
        scanf("%d",&T);
        while(T--) {
            int c=0;
            scanf("%d%d%d%d",&x,&y,&ex,&ey);
            ans=M;
            map[x][y]=1;
            f(x,y,c);
            printf("%d\n",ans);
            map[x][y]=0;
        }
        return 0;
    }

BFS解决方法也贴上  
BFS

#include<stdio.h>
    #include<queue>
    #include<string.h>
    #include<algorithm>
    const int N = 9;
    bool vis[N][N];
    int map[N][N]= {
        1,1,1,1,1,1,1,1,1,
        1,0,0,1,0,0,1,0,1,
        1,0,0,1,1,0,0,0,1,
        1,0,1,0,1,1,0,1,1,
        1,0,0,0,0,1,0,0,1,
        1,1,0,1,0,1,0,0,1,
        1,1,0,1,0,1,0,0,1,
        1,1,0,1,0,0,0,0,1,
        1,1,1,1,1,1,1,1,1,
    };
    using namespace std;
    int px[4]= {
       1,-1,0,0};
    int py[4]= {
       0,0,1,-1};
    int x,y,ex,ey;
    struct note{
        int x,y;
        int step;
    };
    int bfs(){
        note s;
        s.x=x,s.y=y,s.step=0;
        vis[x][y]=true;
        queue<note>que;
        que.push(s);
        while(!que.empty()){
            note now=que.front();
            que.pop();
            if(now.x==ex&&now.y==ey){
                return now.step;
            }
            for(int l=0;l<4;l++){
                note end;
                end.x=now.x+px[l];
                end.y=now.y+py[l];
                end.step=now.step;
                if(vis[end.x][end.y]==false&&map[end.x][end.y]==0){
                    vis[end.x][end.y]=true;
                    end.step+=1;
                    que.push(end);
                }
            }
        }
    }
    int main() {
        int T;
        scanf("%d",&T);
        while(T--){
            memset(vis,false,sizeof(vis));
            scanf("%d%d%d%d",&x,&y,&ex,&ey);
            int ans=bfs();
            printf("%d\n",ans);
        }
        return 0;
    }

[http://acm.nyist.net/JudgeOnline/problem.php?pid=58][http_acm.nyist.net_JudgeOnline_problem.php_pid_58]

[20160728112408449]: /images/20220719/a648304a89a94668ad1e87b339b8046e.png
[20160728112417725]: /images/20220719/e1ac6461795d4b829983503f8dbb026a.png
[http_acm.nyist.net_JudgeOnline_problem.php_pid_58]: http://acm.nyist.net/JudgeOnline/problem.php?pid=58