U5-4-BFS-1

原题链接：67324.4.0U5笔记合集

1943

2025-09-13 20:26:47

发布于：江苏

23阅读

0回复

0点赞

$T1奇怪的电梯$

#include<bits/stdc++.h>
#include<queue>
using namespace std;
int d[100005];
int main(){
    int n,a,b,cnt=0,flag=0;
    int k[10005];
    queue <int> q;
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++){
        cin>>k[i];
        d[i] = -1;
    }
    d[a]=0;
    q.push(a);
    while(q.size()!=0){
        int t=q.front();
        q.pop();        
        if(t+k[t]<=n&&d[t+k[t]]==-1){
            d[t+k[t]] = d[t]+1;
            q.push(t + k[t]);
        }
        if(t-k[t]>=1&&d[t-k[t]]==-1){
            d[t-k[t]] = d[t]+1;
            q.push(t-k[t]);
        }
    }
    cout<<d[b];
    

    return 0;
}

//[【广度优先搜索(一)】奇怪的电梯]

$T2仙岛求药$

#include <bits/stdc++.h>
using namespace std;
struct node{
    int x,y;
};
int m,n;
int ax,ay;
char mp[2005][2005];
int vis[2005][2005],dis[2005][2005];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};

void bfs(int x,int y){
    queue<node> q;
    q.push({x,y});
    while(!q.empty()){
        node a=q.front();
        q.pop();
        if(mp[a.x][a.y]=='*'){
            cout<<dis[a.x][a.y];
            return;
        }
        for(int i=0;i<4;i++){
            int xx=a.x+dx[i],yy=a.y+dy[i];
            if (mp[xx][yy] == '#' || vis[xx][yy]) continue;
//            if(xx>=1&&xx<=m&&yy>=1&&yy<=n&&mp[xx][yy]!='#'&&vis[xx][yy]==0){
                vis[xx][yy]=1;
                dis[xx][yy]=dis[a.x][a.y]+1;
                q.push({xx,yy});
//            }
        }
    }
    cout<<-1;
}

int main(){
    cin >> m >> n;
    memset(mp, '#', sizeof (mp));//
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            cin>>mp[i][j];
            if(mp[i][j]=='@') ax=i,ay=j;
        }
    }
    bfs(ax,ay);
	return 0;
}

/*
[【广度优先搜索(一)】仙岛求药]
题目描述
少年李逍遥的婶婶病了，王小虎介绍他去一趟仙灵岛，向仙女姐姐要仙丹救婶婶。
叛逆但孝顺的李逍遥闯进了仙灵岛，克服了千险万难来到岛的中心，发现仙药摆在了迷阵的深处。
迷阵由 M×N 个方格组成，有的方格内有可以瞬秒李逍遥的怪物，而有的方格内则是安全。
现在李逍遥想尽快找到仙药，显然他应避开有怪物的方格，并经过最少的方格，
而且那里会有神秘人物等待着他。现在要求你来帮助他实现这个目标。

提示
数据范围：(1≤N,M≤2000)

样例说明：
样例一：按照 下右右下下下右右下下 循序移动找到仙药
样例二：按照 上上上上左左上左 循序移动找到仙药
样例三：无法通过移动找到仙药


输入格式
第一行两个非零整数 M 和 N 开始，两者均不大于 2000。
M 表示迷阵行数, N 表示迷阵列数。接下来有 M 行, 每行包含 N 个字符,不同字符分别代表不同含义:

1)‘@’：少年李逍遥所在的位置；
2)‘.’：可以安全通行的方格；
3)‘#’：有怪物的方格；
4)‘*’：仙药所在位置。

输出格式
输出一行，该行包含李逍遥找到仙药需要穿过的最少的方格数目。
如果他不可能找到仙药, 则输出 -1。

样例组
输入#1
8 8
.@##...#
#....#.#
#.#.##..
..#.###.
#.#...#.
..###.#.
...#.*..
.#...###
输出#1
10


输入#2
6 5
.*.#.
.#...
..##.
.....
.#...
....@
输出#2
8


输入#3
9 6
.#..#.
.#.*.#
.####.
..#...
..#...
..#...
..#...
#.@.##
.#..#.

输出#3
-1

*/