luogu P1238 走迷宫--DFS模板好（水）题

题目描述

有一个m*n格的迷宫(表示有m行、n列)，其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件读入这m*n个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息(用-l表示无路)。

优先顺序：左上右下

输入输出格式

输入格式：

第一行是两个数m，n(1<m，n<15)，接下来是m行n列由1和0组成的数据，最后两行是起始点和结束点。

输出格式：

所有可行的路径，描述一个点时用(x，y)的形式，除开始点外，其他的都要用“一>”表示方向。

如果没有一条可行的路则输出-1。

输入输出样例

输入样例#1：

5 6

1 0 0 1 0 1

1 1 1 1 1 1

0 0 1 1 1 0

1 1 1 1 1 0

1 1 1 0 1 1

1 1

5 6

输出样例#1：

(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)

(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)

(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)

(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)

(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)

(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)

(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)

(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)

(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)

(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)

(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)

(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)

对于已经学习过搜索的人来说比较简单吧，有一点小问题就是输出每一步的位置。
　　简单，用个包含俩int变量的结构体完全可以搞定，成立就输出，不成立的话return；
DFS板子：

#include<bits/stdc++.h>

using namespace std;

int dx[]={,-,,};

int dy[]={-,,,};

struct haha{

    int x,y;

}road[];

int vis[][];

int m,n,a[][],qix,qiy,zx,zy,k;

void dfs(int x,int y,int bu){

    if(x==zx&&y==zy){

        k=;

        printf("(%d,%d)",qix,qiy);

        for(int i=;i<bu;i++){

            printf("->(%d,%d)",road[i].x,road[i].y);

        }

        cout<<"\n";

        return ;

    }

    for(int i=;i<;i++){

        int cur=x+dx[i];

        int str=y+dy[i];

        if(cur>=&&cur<=m&&a[cur][str]==&&str>=&&str<=n&&!vis[cur][str]){

            vis[cur][str]=;

            road[bu].x=x+dx[i];

            road[bu].y=y+dy[i];

            dfs(road[bu].x,road[bu].y,bu+);

            road[bu].x-=dx[i];

            road[bu].y-=dy[i];

            vis[cur][str]=;

        }

    }

}

int main()

{

    cin>>m>>n;

    for(int i=;i<=m;i++){

        for(int j=;j<=n;j++){

            cin>>a[i][j];

        }

    }

    cin>>qix>>qiy>>zx>>zy;

    vis[qix][qiy]=;

    dfs(qix,qiy,);

    if(k==)cout<<"-1";

}

巴特西

luogu P1238 走迷宫--DFS模板好（水）题

题目描述

输入输出格式

输入输出样例

最新文章

热门文章