526互联

迷宫题解( •̀ ω •́ )y

发布时间 2024-01-03 19:36:20作者: 努力吧少年^-^

 这道题很明显是一个dfs的问题

这道题首先要在主函数里完成建造迷宫
但在建造迷宫之前，你要把所有的位置标为可以去

memset(a,'.',sizeof(a));

他给你了下标，所以你就可以直接建造迷宫，代码如下

for(int i=1;i<=T;i++){
    cin>>xx>>yy;
    a[xx][yy]='#';
}

不放心可以打一遍输出，最后要记得删掉哦( •̀ ω •́ )y

后面可以把起始点和终点在a数组中标记一下，再把起始点标1，代表来过了

a[sx][sy]='S';
a[fx][fy]='F';
vis[sx][sy]=1;

你还要第一个方向数组，让你可以上下左右的移动（改变坐标）

int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};

下面就可以进入dfs之中了

首先是dfs的出口，很简单就是下标为重点的下标即可

if(x==fx&&y==fy){
    ans++;//可行路线+1
    return ;
}

下面就改变路线（移动）

有4种方向可以走，为上，下，左，右

int nx=x+dx[i],ny=y+dy[i];

判断一下他是否可以走

if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]!='#'&&vis[nx][ny]==0)
//是不是在迷宫之中，是不是障碍，来没来过

如果是的话，就把这个位置标1，代表来过，在进入那个点看看，最后还不要忘了要回溯，因为他又回来了，也就没有走过这个点

vis[nx][ny]=1;
dfs(nx,ny);
vis[nx][ny]=0;

最后，附上完整代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,T,sx,sy,fx,fy,xx,yy,vis[10][10],ans;
char a[10][10];
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
void dfs(int x,int y){
    if(x==fx&&y==fy){
        ans++;
        return ;
    }
    for(int i=0;i<4;i++){
        int nx=x+dx[i],ny=y+dy[i];
        if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]!='#'&&vis[nx][ny]==0){
            vis[nx][ny]=1;
            dfs(nx,ny);
            vis[nx][ny]=0;
        }
    }
}
int main(){
    cin>>n>>m>>T>>sx>>sy>>fx>>fy;
    memset(a,'.',sizeof(a));
    a[sx][sy]='S';
    a[fx][fy]='F';
    vis[sx][sy]=1;
    for(int i=1;i<=T;i++){
        cin>>xx>>yy;
        a[xx][yy]='#';
    }
    dfs(sx,sy);
    cout<<ans;
    return 0;
}