专栏文章

简单最短路(每一条边权值为1)

算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mintkcox
此快照首次捕获于
2025/12/02 08:07
3 个月前
此快照最后确认于
2025/12/02 08:07
3 个月前
查看原文
以下可以实现简单最短路权值为1,#是障碍,.是路。

普通版本

CPP
#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;
} 

升级版本

CPP
#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;
} 

评论

0 条评论,欢迎与作者交流。

正在加载评论...