竞赛讨论区 > BFS搜索即可
头像
牛客192431633号
发布于 昨天 19:55 广东
+ 关注

BFS搜索即可

#include<bits/stdc++.h>

using namespace std;

int row,col;
int start_x,start_y,exit_num=0;

typedef pair<int,int> PII;

const int N=35;

char a[N][N];//记录地图
int step[N][N];//记录走到(N,N)时用的步数
vector<int> ans;//记录走到每个出口时所用的步数

queue<PII> q;

int dx[]={0,1,0,-1}; int dy[]={1,0,-1,0};//上,下,左,右

void bfs(){
    memset(step,-1,sizeof step);//将步数数组初始化为-1
    q.push({start_x,start_y});
    step[start_x][start_y]=0;
    while (q.size())
    {   
        auto t=q.front();q.pop();
        for(int i =0;i<4;i++){
            int tx=t.first+dx[i];int ty=t.second+dy[i];
			//边界判断
            if(tx<1||tx>row||ty<1||ty>col||a[tx][ty]=='*'||a[tx][ty]=='k') continue;
            if(step[tx][ty]!=-1) continue;
            step[tx][ty]=step[t.first][t.second]+1;//到达该位置的步数是上一步的步数+1
			//检测到出口的情况
            if(a[tx][ty]=='e') {
                exit_num++;
                ans.push_back(step[tx][ty]);
                continue;
            } 
            q.push({tx,ty});
        }
    }
}
int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>row>>col;

    for(int i = 1;i <= row;i++){
        for(int j = 1;j <= col;j++){
            cin>>a[i][j];
        }
    }
    //遍历寻找开始位置
    for(int i = 1;i <= row;i++){
        for(int j = 1;j <= col;j++){
            if(a[i][j]=='k'){
                start_x=i,start_y=j;
            }          
        }
    }
    bfs();
	//记得判断是否找到出口
    if(exit_num>0)
    cout<<exit_num<<" "<<ans[0];//ans[0]代表第一个找到的出口,由于bfs的特性,他肯定是最短路径的出口
    else cout<<-1;

    return 0;
}

我自己其实觉得写的有点复杂了,希望有大佬指出可优化的地方

全部评论

(0) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐