宽度有限搜索BFS搜索数及B3625 迷宫寻路 P1451 求细胞数量 B3626 跳跃机器人

这篇具有很好参考价值的文章主要介绍了宽度有限搜索BFS搜索数及B3625 迷宫寻路 P1451 求细胞数量 B3626 跳跃机器人。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

宽度有限搜索BFS搜索

B3625 迷宫寻路

题面

题目描述

机器猫被困在一个矩形迷宫里。

迷宫可以视为一个 n×m 矩阵,每个位置要么是空地,要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。

机器猫初始时位于 (1,1) 的位置,问能否走到 (n,m) 位置。

输入格式

第一行,两个正整数 n,m。

接下来 n 行,输入这个迷宫。每行输入一个长为 m 的字符串,# 表示墙,. 表示空地。

输出格式

仅一行,一个字符串。如果机器猫能走到 (n,m),则输出 Yes;否则输出 No

输入输出样例

输入 #1 

3 5
.##.#
.#...
...#.

输出 #1 

Yes

说明/提示

样例解释

路线如下:(1,1)→(2,1)→(3,1)→(3,2)→(3,3)→(2,3)→(2,4)→(2,5)→(3,5)(1,1)→(2,1)→(3,1)→(3,2)→(3,3)→(2,3)→(2,4)→(2,5)→(3,5)

题解

BFS的思路是从标点(1,1)开始逐层往外扩展,此时我们选择建立一个队列用来保存待访问的点,只要队列非空,判断越界情况和其他非法情况后一直访问相邻位置,可以用一个结构组表示x,y坐标。为了避免重复访问的情况,我们使用vis函数。访问一个点后把vis[x][y]负值与1。到最后如果队列的某个点到了(n,m) 终点,答案设为true,输出这个情况YES。

代码

#include <bits/stdc++.h>
using namespace std;

int n, m, isOk;
char a[105][105];
bool vis[105][105];

struct Pos {
    int x, y;
    Pos(int ax, int ay) {
        x = ax, y = ay;
    }
};

void bfs() {
    queue<Pos> q;

    q.push(Pos(1, 1));

    while(!q.empty()) {
        Pos now = q.front();
        q.pop();

        int x = now.x, y = now.y;

        if(x < 1 || x > n) continue;
        if(y < 1 || y > m) continue;
        if(a[x][y] == '#') continue;

        if(vis[x][y]) continue;
        vis[x][y] = 1;


        if(x == n && y == m) isOk = true;

        q.push(Pos(x + 1, y));
        q.push(Pos(x - 1, y));
        q.push(Pos(x, y + 1));
        q.push(Pos(x, y - 1));
    }

}

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin >> a[i][j];

    bfs();

    if(isOk)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

P1451 求细胞数量

题面

题目描述

一矩形阵列由数字 0 到 9 组成,数字 1 到 9 代表细胞,细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。

输入格式

第一行两个整数代表矩阵大小 n 和 m。

接下来 n 行,每行一个长度为 m 的只含字符 0 到 9 的字符串,代表这个 n×m 的矩阵。

输出格式

一行一个整数代表细胞个数。

输入输出样例

输入 #1

4 10
0234500067
1034560500
2045600671
0000000089

输出 #1

4

题解

这道题的意思,只要相邻的数不是0,那么它和其他相邻的数构成一个细胞,例如样例中的12是一个细胞,23453456456是一个细胞,67,567189,一共四个细胞。这一道题可以用BFS也能用DFS搜索方法。在队列非空的状态依次判断非法情况,避免重复访问,判断是否到终点并寻找答案,继续访问相邻位置。在main循环中bfs之前要判断这个数是否是细胞,是否访问过。Vis可以当访问数组的同时在这类题当成染色“Flood Fill” 

注意事项:

  • 若(x,y)是细胞且无色,则答案+1、并将其所属整个细胞染色
  • BFS 的实现 :当队列非空,访问队首,并将相邻结点人队 

代码

#include <bits/stdc++.h>
using namespace std;
int n, m, ans;
char a[105][105];
bool vis[105][105];
struct Pos {
    int x, y;
    Pos(int ax = 0, int ay = 0) {
        x = ax; // 该结点的 x 值初始化为 ax
        y = ay; // 该结点的 y 值初始化为 ay
    } 
};
// 从 (x, y) 开始 BFS 整个细胞
void bfs(int x, int y) {
    queue<Pos> q;
    q.push(Pos(x, y)); // 将 (x,y) 入队
    while(!q.empty()) { // 当队列非空
        Pos now = q.front(); // 现在处理队首结点
        q.pop(); // 队首出队
        int x = now.x, y = now.y;
        if(x < 1 || x > n) continue;
        if(y < 1 || y > m) continue;
        if(a[x][y] == '0') continue;    // 不是细胞点
        if(vis[x][y]) continue;       // 如果这个点被访问过则跳过
        vis[x][y] = 1;       // 用 vis 数组避免重复访问
        q.push(Pos(x+1, y)); // 将上方结点加入到队列
        q.push(Pos(x-1, y)); // 将下方结点加入到队列
        q.push(Pos(x, y+1)); // 将左方结点加入到队列
        q.push(Pos(x, y-1)); // 将右方结点加入到队列
    }
}
int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> a[i][j];
    for(int x = 1; x <= n; x++)
        for(int y = 1; y <= m; y++)
            if(a[x][y]!='0'&& vis[x][y]==0) { // (x,y) 这个点是细胞点,且未访问过
                ans++;
                bfs(x,y); // 开始对 (x,y) 这个点进行 BFS
            }
    cout << ans << endl;
    return 0;
}
 

B3626 跳跃机器人

题面

题目描述

地上有一排格子,共 n 个位置。机器猫站在第一个格子上,需要取第 n 个格子里的东西。

机器猫当然不愿意自己跑过去,所以机器猫从口袋里掏出了一个机器人!这个机器人的行动遵循下面的规则:

  • 初始时,机器人位于 1 号格子
  • 若机器人目前在 x 格子,那么它可以跳跃到 x−1,x+1,2x 里的一个格子(不允许跳出界)

问机器人最少需要多少次跳跃,才能到达 n 号格子。

输入格式

仅一行,一个正整数,表示 n。

输出格式

仅一行,一个正整数,表示最少跳跃次数。

输入输出样例

输入 #1

30

输出 #1

6

输入 #2

50

输出 #2

7

输入 #3

64

输出 #3

6

输入 #4

63

输出 #4

8

说明/提示

样例解释

第一组样例:
1→2→4→8→16→15→301→2→4→8→16→15→30

第二组样例:
1→2→3→6→12→24→25→501→2→3→6→12→24→25→50

第三组样例:
1→2→4→8→16→32→641→2→4→8→16→32→64

第四组样例:
1→2→4→8→16→32→31→62→631→2→4→8→16→32→31→62→63

请注意在本组样例中,63 不能通过 64−1 得到,因为格子总数为 63,没有第 64 个格子。文章来源地址https://www.toymoban.com/news/detail-642409.html

题解

代码

#include <bits/stdc++.h>
using namespace std;
struct Pos {
    int x, cost;
    Pos(int ax = 0, int acost = 0) {
        x = ax, cost = acost;
    }
};
int n;
bool vis[1000005];
void bfs() {
    int x=1, cost=0;
    queue <Pos> q;
    q.push(Pos(x,cost)); 
    while(!q.empty()) {
        Pos now = q.front();
        q.pop();
        int x = now.x, cost = now.cost;
        if(x<1||x>n) // 处理越界,如果 x 不在 [1,n] 范围内
            continue;           
        if(vis[x]) // 用 vis 数组判断重复
            continue; 
        vis[x] = 1; // 用 vis 数组标记这个数字被访问过

        if(x == n) {
            cout << cost << endl;
            return;
        }
        q.push(Pos(x-1, cost+1));
        q.push(Pos(x+1,cost+1));
        q.push(Pos(2*x, cost+1));
    }
}
int main() {
    cin >> n;
    bfs();
    return 0;
} 

到了这里,关于宽度有限搜索BFS搜索数及B3625 迷宫寻路 P1451 求细胞数量 B3626 跳跃机器人的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法手札】深入理解宽度遍历(bfs)和深度遍历(dfs)搜索

        算法的重要性不言而喻,现在我们的生活也已经离不开各种算法,一个好的算法能大大提高程序的运行效率,是学习编程的一个重要模块,而遍历算法也是算法里的一个大的模块,今天我们一起来学习一下深度遍历算法(depth first search)和 广度优先遍历(broad first searc

    2024年02月21日
    浏览(43)
  • A*算法求解迷宫寻路问题实验

    一、实验目标: 熟悉和掌握A*算法实现迷宫寻路功能,要求掌握启发式函数的编写以及各类启发式函数效果的比较。 二、实验内容与完成情况: 寻路问题常见于各类游戏中角色寻路、三维虚拟场景中运动目标的路径规划、机器人寻路等多个应用领域。迷宫寻路问题是在以方

    2024年02月04日
    浏览(37)
  • 基于深度强化学习(DQN)的迷宫寻路算法

    QLearning方法有着明显的局限性,当状态和动作空间是离散的且维数不高时可使用Q-Table存储每个状态动作的Q值,而当状态和动作时高维连续时,该方法便不太适用。可以将Q-Table的更新问题变成一个函数拟合问题,通过更新参数θ使得Q函数逼近最优Q值。DL是解决参数学习的有效

    2023年04月22日
    浏览(73)
  • unity有限状态机和模糊状态机(怪物AI、自动寻路)

    自动寻路步骤: 1、把场景中不同的物体勾选static 2、烘培寻路网格 3、添加NavMeshAgent组件 4、给需要寻路的物体添加脚本 游戏中有限状态机的体现:小怪的巡逻和追逐功能 模糊状态机的体现:当玩家离小怪比较近时,小怪会追逐玩家,当玩家离小怪比较远时小怪会停止追逐玩

    2024年02月04日
    浏览(50)
  • 基于RL(Q-Learning)的迷宫寻路算法

    强化学习是一种机器学习方法,旨在通过智能体在与环境交互的过程中不断优化其行动策略来实现特定目标。与其他机器学习方法不同,强化学习涉及到智能体对环境的观测、选择行动并接收奖励或惩罚。因此,强化学习适用于那些需要自主决策的复杂问题,比如游戏、机器

    2023年04月21日
    浏览(42)
  • 迷宫问题-DFS-BFS

    🚀学习过算法程序设计的应该都学习过迷宫这个问题,迷宫问题主要设计的算法就是DFS-深度优先遍历和BFS-广度优先遍历。 🚀在一个二维数组中,元素为1的位置表示这个位置是墙,0表示有通路,迷宫的入口和出口都是0(否则不会有路径能出去),并且路径不唯一。例如下

    2023年04月22日
    浏览(43)
  • 算法:BFS宽度优先遍历

    本篇总结的是BFS算法,BFS算法相比起DFS算法来说还是比较简单的 这里提供一种双端队列的做法,也可以在合适的层数逆序

    2024年02月21日
    浏览(52)
  • 【算法】(BFS/DFS)迷宫路径问题(C语言)

    题目 :现有一迷宫如下图所示,蓝色部分为墙壁,白色部分为通路,入口在左上角(1,1)处,出口在右下角(8,8)处,试找出一条路径以通过该迷宫(路径不能重叠)。 分析 : ① 使用二维数组来存储迷宫,墙用 1 表示,路用 0 表示,如下图所示: 为与题目中的入口坐标

    2024年02月07日
    浏览(82)
  • BFS4专题 迷宫最短路径(输出路径)

    输入 输出         这里刚开始看的时候会可能有点复杂了,因为是递归。 但是只要理解了含义,脑袋里模拟一下还是可以理解的。首先还是 之前那样 BFS 常规搜索 只是这里不用输出步数了,所以我们可以省略一层循环,直接搜索求路径。 求路径的方法核心思想就是 记录每

    2024年02月11日
    浏览(36)
  • 迷宫的最少步数and最短路径(BFS)

    题目描述 一个迷宫由 R 行 C 列格子组成,有的格子里有障碍物,不能走;有的格子是空地,可以走。 给定一个迷宫,求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走,不能斜着走。 输入 第一行是两个整数,R 和 C ,代表迷宫的

    2024年02月14日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包