简单最短路（每一条边权值为1）

Alen_0501 · 2025-09-22 17:10:48 · 算法·理论

以下可以实现简单最短路权值为1，#是障碍，.是路。

普通版本

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,dx[]={-1,1,0,0},dy[]={0,0,1,-1};
bool f[1004][1004],flag=false;
char c[1004][1004];
struct str{
    int x,y,cut;
};
struct point{
    int x,y;
}dist[1004][1004];
void print(point nn){
    if(dist[nn.x][nn.y].x==0 && dist[nn.x][nn.y].y==0){
        cout<<nn.x<<" "<<nn.y<<endl;
        return ;
    }
    print(dist[nn.x][nn.y]);
    cout<<nn.x<<" "<<nn.y<<endl;
    return ;
}

signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>c[i][j];
            if(c[i][j]=='#')  f[i][j]=true;
        }
    }
    queue<str> q;
    q.push({1,1,0});
    dist[1][1]={0,0};
    f[1][1]=true;
    while(!q.empty()){
        str nn=q.front();
        q.pop();
        if(nn.x==n && nn.y==m){
            cout<<"找到了！"<<endl;
            /*
            for(int i=1;i<=n;i++){
                for(int j=1;j<=m;j++){
                    cout<<dist[i][j].x<<" "<<dist[i][j].y<<"好了";
                }
                cout<<endl;
            }
            */
            print({nn.x,nn.y});
            flag=true;
            break;
        }
        for(int i=0;i<4;i++){
            int nx=nn.x+dx[i],ny=nn.y+dy[i];
            if(nx<1 || nx>n || ny<1 || ny>m)  continue;
            if(c[nx][ny]=='#')  continue;
            if(f[nx][ny])  continue;
            q.push({nx,ny,nn.cut+1});
            f[nx][ny]=true;
            dist[nx][ny]={nn.x,nn.y};
        }
    }
    if(flag)  cout<<"寻找完成！";
    else  cout<<"无法找到路径！";
    return 0;
} 

升级版本

#include<bits/stdc++.h>
#include<windows.h>
#define int long long
using namespace std;
int n,m,dx[]={-1,1,0,0},dy[]={0,0,1,-1};
bool f[1004][1004],flag=false;
char c[1004][1004];
struct str{
    int x,y,cut;
};
struct point{
    int x,y;
}dist[1004][1004];
void print(point nn){
    if(dist[nn.x][nn.y].x==0 && dist[nn.x][nn.y].y==0){
        cout<<nn.x<<" "<<nn.y<<endl;
        Sleep(100);
        return ;
    }
    print(dist[nn.x][nn.y]);
    cout<<nn.x<<" "<<nn.y<<endl;
    Sleep(100);
    return ;
}

signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>c[i][j];
            if(c[i][j]=='#')  f[i][j]=true;
        }
    }
    if(f[1][1] || f[n][m]){
        cout<<"无法找到路径！";
        exit(0);
    }
    queue<str> q;
    q.push({1,1,0});
    dist[1][1]={0,0};
    f[1][1]=true;
    while(!q.empty()){
        str nn=q.front();
        q.pop();
        if(nn.x==n && nn.y==m){
            cout<<"找到了！"<<endl;
            print({nn.x,nn.y});
            flag=true;
            break;
        }
        for(int i=0;i<4;i++){
            int nx=nn.x+dx[i],ny=nn.y+dy[i];
            if(nx<1 || nx>n || ny<1 || ny>m)  continue;
            if(c[nx][ny]=='#')  continue;
            if(f[nx][ny])  continue;
            q.push({nx,ny,nn.cut+1});
            f[nx][ny]=true;
            dist[nx][ny]={nn.x,nn.y};
        }
    }
    if(flag)  cout<<"寻找完成！";
    else  cout<<"无法找到路径！";
    return 0;
}