路径记忆问题

参考链接：https://blog.csdn.net/weixin_44965308/article/details/104928695 

练习题目：迷宫问题 POJ - 3984 //听说是水题，直接打印都可以过去的那种

方式一：

dfs暴力搜索

 几个月前的代码了，当时太菜鸡了，能看懂的就看懂把，bfs的能够跑更大的图，还是推荐bfs

#include<iostream>

using namespace std;
int aa[4][2]={{0,1},{1,0}};//两个方向，是图的复杂度很低可以过去，正确的应该是搜索四个方向
int mp[6][6],a=1;
int ans[100]={0},vis[100]={0};
void dfs(int x,int y){
    if(x==4&&y==4){
        for(int i=0;i<a;i++)
            printf("(%d, %d)\n",ans[i],vis[i]);
        return ;
    }
    for(int i=0;i<2;i++){
        int dx=x+aa[i][0];
        int dy=y+aa[i][1];
        if(!mp[dx][dy]&&dx>=0&&dy<=4&&dy>=0&&dy<=4){
            ans[a]=dx;
            vis[a++]=dy;
            dfs(dx,dy);//数据弱就没有回溯，强点肯定要回溯，留下之后填坑把


        }
    }
}

int main(){
    for(int i=0;i<5;i++)
        for(int j=0;j<5;j++)
            cin>>mp[i][j];
    dfs(0,0);
    return 0;
}

方式二：

bfs两次搜索(一次正向，一次反向)每一次跑到了最短路就可以该点

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl "\n"
const int N=10;
int dis[N][N],dis1[N][N];//正向路径，反向路径记录了走(i,j)需要的步骤
int vis[N][N],mapp[N][N];//标记数组，图数组
int aa[4][2]={{1,0},{0,1},{0,-1},{-1,0}};//方向 数组
int mapp1[N][N],ans;//标记图数组可以走记作1，不能走都是0

struct node{
    int x,y,z;
};//保存当前坐标x,y和步数z

bool rule(int x,int y){
    return x>=1&&x<=5&&y>=1&&y<=5&&mapp[x][y]!=1;
}//判断越界和可以走

void bfs(int dx,int dy,int fx,int fy,int ma[][N]){//起点x,y,终点x,y,二维数组
    memset(vis,0,sizeof vis);//清空标记
    queue<node>st;
    st.push({dx,dy,0});//poj可能会卡这个
    while(!st.empty()){
        node cur=st.front();
        st.pop();
        int x=cur.x,y=cur.y,z=cur.z;
        ma[x][y]=z,vis[x][y]=1;//将dis或者dis1填写步数，vis表示来过这里
        if(x==fx&&y==fy) return ;//停止判断
        for(int i=0;i<4;i++){
            int ax=x+aa[i][0],ay=y+aa[i][1],az=z+1;
            if(rule(ax,ay)&&!vis[ax][ay]) st.push({ax,ay,az});//没有越界，可以走，没有走过
        }
    }
}

void print(int x,int y,int step){//打印路径
    cout<<"("<<x-1<<", "<<y-1<<")"<<endl;
    if(step==ans+1)return ;//如果打印结束了总共的路径就停下了
    for(int i=0;i<4;i++){
        int dx=x+aa[i][0],dy=y+aa[i][1];
        if(rule(dx,dy)&&mapp1[dx][dy]){//没有越界，原来可以走，mapp1可以走
            if(dis[dx][dy]<dis[x][y])continue;//防止成环，dis表示走到(i,j)的步骤，这里防止走回去，所以需要剪枝
            print(dx,dy,step+1);
        }
    }
}

int main(){
    IOS;//关闭数据流
    for(int i=1;i<=5;i++)
        for(int j=1;j<=5;j++)
            cin>>mapp[i][j];//读入地图
    bfs(1,1,5,5,dis);//正向走图
    bfs(5,5,1,1,dis1);//反向走图
    ans=dis[5][5];
    memset(mapp1,0,sizeof mapp1);
    for(int i=1;i<=5;i++)
        for(int j=1;j<=5;j++)
            if(dis[i][j]+dis1[i][j]==ans)
                mapp1[i][j]=1;
    print(1,1,1);
    return 0;
}

方式三：

stack方向打印路径+bfs跑图(记录方向)

stack就是普通的,bfs加上了记录走到(i,j)的状态，以为走到每一个点，需要标记，也就代表走到(i,j)只有一个方向
所以开一个数组fa[N][N]保存走到当前点的状态

#include<iostream>
#include<stack>
#include<queue>
using namespace std;
#define endl "\n"
const int N=100;
int aa[N][N],vis[N][N],fa[10][10];//地图数组，标记数组，上一个状态的数组
int dis[4][2]={{1,0},{0,1},{0,-1},{-1,0}};//下，右，左，上，方向随意
int ax=1,ay=1,ex=5,ey=5;//起点x,y，终点x,y

struct node{
    int x,y;//当前坐标x,y
};

bool rule(int x,int y){
    return !vis[x][y]&&!aa[x][y]&&x>=1&&x<=5&&y>=1&&y<=5;
}//防止越界，防止走过，防止不能走

void bfs(){//正常的bfs
    queue<node>st;
    st.push({1,1});
    fa[1][1]=-1;//起点设置为-1，方便~(-1)->0跳出条件
    while(!st.empty()){
        node cur=st.front();
        st.pop();
        int x=cur.x,y=cur.y;
        vis[x][y]=1;//vis很重要，取决了你回溯的想法
        for(int i=0;i<4;i++){
            int dx=x+dis[i][0],dy=y+dis[i][1];
            if(rule(dx,dy)){
                st.push({dx,dy});
                fa[dx][dy]=i;//标记到这个点上一个状态，多了一行
            }
        }
    }
}

void print(){//因为跑图的时候vis了，所以到(i,j)的方向只有一个
    stack<node>s;//栈可以先进后出，用来回溯肯定最好
    int temp=fa[ex][ey];//保存终点的状态，也就是到达(5,5)的dis状态
    s.push({ex,ey});//压入终点的方向
    while(~temp){//也就是搜索到当temp=-1的时候停止，因为我们标记了fa[1][1]=-1;
        ex-=dis[temp][0],ey-=dis[temp][1];//找到到(i,j)的上一个点
        s.push({ex,ey});//压入上一个点 
        temp=fa[ex][ey];
    }//开始打印
    while(s.size()){
        node cur=s.top();
        s.pop();
        cout<<"("<<cur.x-1<<", "<<cur.y-1<<")"<<endl;
    }
}

int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n=5,m;
    for(int i=1;i<=5;i++)
        for(int j=1;j<=5;j++){
            cin>>aa[i][j];//存图
            if(aa[i][j]==1)fa[i][j]=-1;//当前点没法走所以就直接pass掉
        }
    bfs();
    print();
    return 0;
}