AcWing 1076. 迷宫问题

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1076. 迷宫问题原题链接简单

作者：

ZTEG , 2019-11-08 15:05:21 , 所有人可见 , 阅读 4130

15

3

思路

反着跑一遍BFS并标记
正着再跑一遍BFS并输出

#include<bits/stdc++.h>
using namespace std;
int f[1005][1005],t,tx,ty;
int book[1005][1005];
int kx[4]={0,0,1,-1};
int ky[4]={1,-1,0,0};
struct vivo{
    int x,y;
}mi;
queue< vivo > v;
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            cin>>t;
            if(t)
            {
                f[i][j]=-1;
                book[i][j]=0;
            }
            else
            {
                f[i][j]=0;
                book[i][j]=1;
            }
        }
    book[n][n]=0;
    f[n][n]=1;
    mi.x=n;
    mi.y=n;
    v.push(mi);
    while(v.size())
    {
        for(int i=0;i<4;i++)
        {
            tx=v.front().x+kx[i];
            ty=v.front().y+ky[i];
            if(tx>0&&ty>0&&tx<=n&&ty<=n&&book[tx][ty])
            {
                book[tx][ty]=0;
                mi.x=tx;
                mi.y=ty;
                v.push(mi);
                f[tx][ty]=f[v.front().x][v.front().y]+1;
            }
        }
        v.pop();
    }
    mi.x=1;
    mi.y=1;
    v.push(mi);
    printf("0 0\n");
    while(v.size())
    {
        for(int i=0;i<4;i++)
        {
            tx=v.front().x+kx[i];
            ty=v.front().y+ky[i];
            if(tx>0&&ty>0&&tx<=n&&ty<=n&&f[tx][ty]==f[v.front().x][v.front().y]-1)
            {
                printf("%d %d\n",tx-1,ty-1);
                mi.x=tx;
                mi.y=ty;
                v.push(mi);
                break;
            }
        }
        v.pop();
    }
    return 0;
}

9 评论

辣鸡号航母 2022-08-12 23:15

有人试过用dfs回溯的吗？？

uuioyc 2022-08-15 22:02

###bfs+dfs

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

const int N=1010;

bool st[N][N];
int g[N][N],f[N][N];
int n;

vector<PII> ans;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
void bfs(){

    queue<PII> q;
    q.push({1,1});
    st[1][1]=true;

    while(q.size()){
        PII t=q.front();
        q.pop();
        int x=t.first,y=t.second;

        if(x==n&&y==n)break;
        for(int i=0;i<4;++i){
            int nx=x+dx[i],ny=dy[i]+y;
            if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&!st[nx][ny]&&g[nx][ny]==0){
                q.push({nx,ny});
                f[nx][ny]=f[x][y]+1;
                st[nx][ny]=true;
            }
        }
    }
}

void dfs(int x,int y){
    ans.push_back({x-1,y-1});
    for(int i=0;i<4;++i){
        int nx=x+dx[i],ny=dy[i]+y;
            if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&f[nx][ny]+1==f[x][y]&&g[nx][ny]==0){
                dfs(nx,ny);
                break;
            }
    }
}
int main(){

    cin>>n;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            scanf("%d",&g[i][j]);
        }
    }
    bfs();
    dfs( n, n);
    reverse(ans.begin(),ans.end());
    for(int i=0;i<ans.size();++i){
        cout<<ans[i].first<<" "<<ans[i].second<<endl;
    }
    return 0;
}