【算法笔记自学】第 8 章 提高篇（2）——搜索专题

8.1深度优先搜索（DFS）

#include <cstdio>

const int MAXN = 5;
int n, m, maze[MAXN][MAXN];
bool visited[MAXN][MAXN] = {false};
int counter = 0;

const int MAXD = 4;
int dx[MAXD] = {0, 0, 1, -1};
int dy[MAXD] = {1, -1, 0, 0};

bool isValid(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m && maze[x][y] == 0 && !visited[x][y];
}

void DFS(int x, int y) {
    if (x == n - 1 && y == m - 1) {
        counter++;
        return;
    }
    visited[x][y] = true;
    for (int i = 0; i < MAXD; i++) {
        int nextX = x + dx[i];
        int nextY = y + dy[i];
        if (isValid(nextX, nextY)) {
            DFS(nextX, nextY);
        }
    }
    visited[x][y] = false;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &maze[i][j]);
        }
    }
    DFS(0, 0);
    printf("%d", counter);
    return 0;
}

#include <cstdio>

const int MAXN = 5;
int n, m, k, maze[MAXN][MAXN];
bool visited[MAXN][MAXN] = {false};
bool canReach = false;

const int MAXD = 4;
int dx[MAXD] = {0, 0, 1, -1};
int dy[MAXD] = {1, -1, 0, 0};

bool isValid(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m && maze[x][y] == 0 && !visited[x][y];
}

void DFS(int x, int y, int step) {
    if (canReach) {
        return;
    }
    if (x == n - 1 && y == m - 1) {
        if (step == k) {
            canReach = true;
        }
        return;
    }
    visited[x][y] = true;
    for (int i = 0; i < MAXD; i++) {
        int nextX = x + dx[i];
        int nextY = y + dy[i];
        if (step < k && isValid(nextX, nextY)) {
            DFS(nextX, nextY, step + 1);
        }
    }
    visited[x][y] = false;
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &maze[i][j]);
        }
    }
    DFS(0, 0, 0);
    printf(canReach ? "Yes" : "No");
    return 0;
}

#include <cstdio>

const int MAXN = 5;
const int INF = 0x3f3f3f3f;
int n, m, maze[MAXN][MAXN];
bool visited[MAXN][MAXN] = {false};
int maxValue = -INF;

const int MAXD = 4;
int dx[MAXD] = {0, 0, 1, -1};
int dy[MAXD] = {1, -1, 0, 0};

bool isValid(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m && !visited[x][y];
}

void DFS(int x, int y, int nowValue) {
    if (x == n - 1 && y == m - 1) {
        if (nowValue > maxValue) {
            maxValue = nowValue;
        }
        return;
    }
    visited[x][y] = true;
    for (int i = 0; i < MAXD; i++) {
        int nextX = x + dx[i];
        int nextY = y + dy[i];
        if (isValid(nextX, nextY)) {
            int nextValue = nowValue + maze[nextX][nextY];
            DFS(nextX, nextY, nextValue);
        }
    }
    visited[x][y] = false;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &maze[i][j]);
        }
    }
    DFS(0, 0, maze[0][0]);
    printf("%d", maxValue);
    return 0;
}

#include <cstdio>
#include <vector>
#include <utility>
using namespace std;

typedef pair<int, int> Position;

const int MAXN = 5;
const int INF = 0x3f;
int n, m, maze[MAXN][MAXN];
bool visited[MAXN][MAXN] = {false};
int maxValue = -INF;
vector<Position> tempPath, optPath;

const int MAXD = 4;
int dx[MAXD] = {0, 0, 1, -1};
int dy[MAXD] = {1, -1, 0, 0};

bool isValid(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m && !visited[x][y];
}

void DFS(int x, int y, int nowValue) {
    if (x == n - 1 && y == m - 1) {
        if (nowValue > maxValue) {
            maxValue = nowValue;
            optPath = tempPath;
        }
        return;
    }
    visited[x][y] = true;
    for (int i = 0; i < MAXD; i++) {
        int nextX = x + dx[i];
        int nextY = y + dy[i];
        if (isValid(nextX, nextY)) {
            int nextValue = nowValue + maze[nextX][nextY];
            tempPath.push_back(Position(nextX, nextY));
            DFS(nextX, nextY, nextValue);
            tempPath.pop_back();
        }
    }
    visited[x][y] = false;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &maze[i][j]);
        }
    }
    tempPath.push_back(Position(0, 0));
    DFS(0, 0, maze[0][0]);
    for (int i = 0; i < optPath.size(); i++) {
        printf("%d %d\n", optPath[i].first + 1, optPath[i].second + 1);
    }
    return 0;
}

#include <cstdio>

const int MAXN = 5;
const int INF = 0x3f;
int n, m, maze[MAXN][MAXN], isWall[MAXN][MAXN];
bool visited[MAXN][MAXN] = {false};
int maxValue = -INF;

const int MAXD = 4;
int dx[MAXD] = {0, 0, 1, -1};
int dy[MAXD] = {1, -1, 0, 0};

bool isValid(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m && !isWall[x][y] && !visited[x][y];
}

void DFS(int x, int y, int nowValue) {
    if (x == n - 1 && y == m - 1) {
        if (nowValue > maxValue) {
            maxValue = nowValue;
        }
        return;
    }
    visited[x][y] = true;
    for (int i = 0; i < MAXD; i++) {
        int nextX = x + dx[i];
        int nextY = y + dy[i];
        if (isValid(nextX, nextY)) {
            int nextValue = nowValue + maze[nextX][nextY];
            DFS(nextX, nextY, nextValue);
        }
    }
    visited[x][y] = false;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &isWall[i][j]);
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &maze[i][j]);
        }
    }
    DFS(0, 0, maze[0][0]);
    printf("%d", maxValue);
    return 0;
}

8.2广度优先搜索（BFS）

 

#include <cstdio>
#include <queue>
using namespace std;

const int MAXN = 100000;
bool inQueue[MAXN + 1] = {false};

int getStep(int n) {
    int step = 0;
    queue<int> q;
    q.push(1);
    while (true) {
        int cnt = q.size();
        for (int i = 0; i < cnt; i++) {
            int front = q.front();
            q.pop();
            if (front == n) {
                return step;
            }
            inQueue[front] = true;
            if (front * 2 <= n && !inQueue[front * 2]) {
                q.push(front * 2);
            }
            if (front + 1 <= n && !inQueue[front + 1]) {
                q.push(front + 1);
            }
        }
        step++;
    }
}

int main() {
    int n, step = 0;
    scanf("%d", &n);
    printf("%d", getStep(n));
    return 0;
}

#include <cstdio>
#include <queue>
#include <utility>
using namespace std;

typedef pair<int, int> Position;

const int MAXN = 100;
int n, m, matrix[MAXN][MAXN];
bool inQueue[MAXN][MAXN] = {false};

const int MAXD = 4;
int dx[MAXD] = {0, 0, 1, -1};
int dy[MAXD] = {1, -1, 0, 0};

bool canVisit(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m && matrix[x][y] == 1 && !inQueue[x][y];
}

void BFS(int x, int y) {
    queue<Position> q;
    q.push(Position(x, y));
    inQueue[x][y] = true;
    while (!q.empty()) {
        Position front = q.front();
        q.pop();
        for (int i = 0; i < MAXD; i++) {
            int nextX = front.first + dx[i];
            int nextY = front.second + dy[i];
            if (canVisit(nextX, nextY)) {
                inQueue[nextX][nextY] = true;
                q.push(Position(nextX, nextY));
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &matrix[i][j]);
        }
    }
    int counter = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == 1 && !inQueue[i][j]) {
                BFS(i, j);
                counter++;
            }
        }
    }
    printf("%d", counter);
    return 0;
}

#include <cstdio>
#include <queue>
#include <utility>
using namespace std;

typedef pair<int, int> Position;

const int MAXN = 100;
int n, m, maze[MAXN][MAXN];
bool inQueue[MAXN][MAXN] = {false};

const int MAXD = 4;
int dx[MAXD] = {0, 0, 1, -1};
int dy[MAXD] = {1, -1, 0, 0};

bool canVisit(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m && maze[x][y] == 0 && !inQueue[x][y];
}

int BFS(int x, int y) {
    queue<Position> q;
    q.push(Position(x, y));
    inQueue[x][y] = true;
    int step = 0;
    while (!q.empty()) {
        int cnt = q.size();
        while (cnt--) {
            Position front = q.front();
            q.pop();
            if (front.first == n - 1 && front.second == m - 1) {
                return step;
            }
            for (int i = 0; i < MAXD; i++) {
                int nextX = front.first + dx[i];
                int nextY = front.second + dy[i];
                if (canVisit(nextX, nextY)) {
                    inQueue[nextX][nextY] = true;
                    q.push(Position(nextX, nextY));
                }
            }
        }
        step++;
    }
    return -1;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &maze[i][j]);
        }
    }
    int step = BFS(0, 0);
    printf("%d", step);
    return 0;
}

#include <cstdio>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

typedef pair<int, int> Position;

const int MAXN = 100;
int n, m, maze[MAXN][MAXN];
bool inQueue[MAXN][MAXN] = {false};
Position pre[MAXN][MAXN];

const int MAXD = 4;
int dx[MAXD] = {0, 0, 1, -1};
int dy[MAXD] = {1, -1, 0, 0};

bool canVisit(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m && maze[x][y] == 0 && !inQueue[x][y];
}

void BFS(int x, int y) {
    queue<Position> q;
    q.push(Position(x, y));
    inQueue[x][y] = true;
    while (!q.empty()) {
        Position front = q.front();
        q.pop();
        if (front.first == n - 1 && front.second == m - 1) {
            return;
        }
        for (int i = 0; i < MAXD; i++) {
            int nextX = front.first + dx[i];
            int nextY = front.second + dy[i];
            if (canVisit(nextX, nextY)) {
                pre[nextX][nextY] = Position(front.first, front.second);
                inQueue[nextX][nextY] = true;
                q.push(Position(nextX, nextY));
            }
        }
    }
}

void printPath(Position p) {
    Position prePosition = pre[p.first][p.second];
    if (prePosition == Position(-1, -1)) {
        printf("%d %d\n", p.first + 1, p.second + 1);
        return;
    }
    printPath(prePosition);
    printf("%d %d\n", p.first + 1, p.second + 1);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &maze[i][j]);
        }
    }
    fill(pre[0], pre[0] + n * m, Position(-1, -1));
    BFS(0, 0);
    printPath(Position(n - 1, m - 1));
    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/781393.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

docker中实现多机redis主从集群

docker中实现多机redis主从集群

redis主从集群是每个使用redis的小伙伴都必需知道的&#xff0c;那如何在docker中快速配置呢&#xff1f;这篇来教你快速上手&#xff0c;跟着复制完全就能用&#xff01;&#xff01; 1. 前置准备 1.1 docker安装 以防有小伙伴没预先安装docker&#xff0c;这里提供安装步骤…
阅读更多...
驾校管理系统设计

驾校管理系统设计

驾校管理系统设计旨在提高驾校运营效率、学员管理、教练安排、考试预约、财务结算等方面的能力。以下是一个基本的设计框架&#xff0c;包括关键模块和数据表设计&#xff1a; 1. 系统架构设计 前端界面&#xff1a;提供给学员、教练和管理员使用的Web界面或移动应用&#xf…
阅读更多...
CGAL计算凸包（OSG进行可视化）

CGAL计算凸包（OSG进行可视化）

目录 一、什么是凸包 二、运行步骤 1、安装依赖项 2、编译osg库 3、运行代码 4、运行截图 一、什么是凸包 凸包是计算几何中的一个基本概念，用来描述一个点集的最小凸包围形。具体来说，给定一个点集，凸包是包含该点集的最小凸多边形或凸多面体。 二维凸包：在二维平面…
阅读更多...
# 三 JS的流程控制和函数

# 三 JS的流程控制和函数

三 JS的流程控制和函数 3.1 JS分支结构 if结构 这里的if结构几乎和JAVA中的一样,需要注意的是 if()中的非空字符串会被认为是trueif()中的非零数字会被认为是true 代码 if(false){// 非空字符串 if判断为trueconsole.log(true) }else{console.log(false) } if(){// 长度为0…
阅读更多...
昇思MindSpore学习笔记4-03生成式--Diffusion扩散模型

昇思MindSpore学习笔记4-03生成式--Diffusion扩散模型

摘要&#xff1a; 记录昇思MindSpore AI框架使用DDPM模型给图像数据正向逐步添加噪声&#xff0c;反向逐步去除噪声的工作原理和实际使用方法、步骤。 一、概念 1. 扩散模型Diffusion Models DDPM(denoising diffusion probabilistic model) &#xff08;无&#xff09;条件…
阅读更多...
数据库系统原理练习 | 作业1-第1章绪论（附答案）

数据库系统原理练习 | 作业1-第1章绪论（附答案）

整理自博主本科《数据库系统原理》专业课完成的课后作业&#xff0c;以便各位学习数据库系统概论的小伙伴们参考、学习。 *文中若存在书写不合理的地方&#xff0c;欢迎各位斧正。 专业课本&#xff1a; 目录 一、选择题 二&#xff1a;简答题 三&#xff1a;综合题 一、选择…
阅读更多...
【数据库】MySQL基本操作语句

【数据库】MySQL基本操作语句

目录 一、SQL语句 1.1 SQL分类 1.2 SQL语言规范 1.3 数据库对象与命名 1.3.1 数据库的组件(对象)&#xff1a; 1.3.2 命名规则&#xff1a; 1.4 SQL语句分类 二、基本命令 2.1 查看帮助信息 2.2 查看支持的字符集 2.3 查看默认使用的字符集 2.4 修改默认字符集 2.5…
阅读更多...
Camera Raw：编辑 - 校准

Camera Raw：编辑 - 校准

Camera Raw “编辑”模块中的校准 Calibration面板设计初衷是校准相机所采集的 R、G、B 色彩信息&#xff0c;使相机的 RGB 色域范围尽可能与标准 RGB 色域范围重合。不过&#xff0c;现在多用于创意调色。通过调整红、绿、蓝三个原色的色相和饱和度&#xff0c;以及阴影的色调…
阅读更多...
HTTP长连接

HTTP长连接

长连接优点 HTTP为什么要开启长连接呢？ 主要是为了节省建立的时间，请求可以复用同一条TCP链路，不用重复进行三握+四挥 如果没有长连接，每次请求都做三握+四挥 如果有长链接，在一个 TCP 连接中可以持续发送多份数据而不会断开连接，即请求可以复用TCP链路 长连接缺点 …
阅读更多...
数字信号处理及MATLAB仿真（3）——量化的其他概念

数字信号处理及MATLAB仿真（3）——量化的其他概念

上回书说到AD转换的两个步骤——量化与采样两个步骤。现在更加深入的去了解以下对应的概念。学无止境&#xff0c;要不断地努力才有好的收获。万丈高楼平地起&#xff0c;唯有打好基础&#xff0c;才能踏实前行。 不说了&#xff0c;今天咱们继续说说这两个步骤&#xff0c;首先…
阅读更多...
归并排序的实现（递归与非递归）

归并排序的实现（递归与非递归）

概念 基本思想&#xff1a;归并排序&#xff08;MERGE-SORT&#xff09;是建立在归并操作上的一种有效的排序算法,该算法是采用分治法&#xff08;Divide andConquer&#xff09;的一个非常典型的应用。将已有序的子序列合并&#xff0c;得到完全有序的序列&#xff1b;即先使…
阅读更多...
一篇文章搞懂qt图形视图框架setRect和setPos函数的意义

一篇文章搞懂qt图形视图框架setRect和setPos函数的意义

setRect()函数 三个坐标系我就不多说了&#xff0c;view原点默认在左上角&#xff0c;scene和item的原点默认都在中心位置。 注意&#xff1a;此函数并不能设置一个item的位置&#xff0c;我的理解是当一个item调用该函数时&#xff0c;会构建一个一个item的坐标系&#xff0c…
阅读更多...
秋招提前批面试经验分享（下）

秋招提前批面试经验分享（下）

⭐️感谢点开文章&#x1f44b;&#xff0c;欢迎来到我的微信公众号&#xff01;我是恒心&#x1f60a; 一位热爱技术分享的博主。如果觉得本文能帮到您&#xff0c;劳烦点个赞、在看支持一下哈&#x1f44d;&#xff01; ⭐️我叫恒心&#xff0c;一名喜欢书写博客的研究生在读…
阅读更多...
vue3+antd 实现点击按钮弹出对话框

vue3+antd 实现点击按钮弹出对话框

格式1&#xff1a;确认对话框 按钮&#xff1a; 点击按钮之后&#xff1a; 完整代码&#xff1a; <template><div><a-button click"showConfirm">Confirm</a-button></div> </template> <script setup> import {Mod…
阅读更多...
关于Web开发的详细介绍

关于Web开发的详细介绍

目录 一、什么是Web&#xff1f; 二、Web网站的工作流程和开发模式 &#xff08;1&#xff09;简单介绍 &#xff08;2&#xff09;工作流程 1、第一步 2、第二步 &#xff08;3&#xff09;Web网站的开发模式 1、前后端分离开发模式 ​编辑2、混合开发模式 三、开发W…
阅读更多...
DPDK源码分析之(1)libmbuf模块

DPDK源码分析之(1)libmbuf模块

DPDK源码分析之(1)libmbuf模块 Author&#xff1a;OnceDay Date&#xff1a;2024年7月2日 漫漫长路&#xff0c;有人对你笑过嘛… 全系列文档可参考专栏&#xff1a;源码分析_Once-Day的博客-CSDN博客 参考文档&#xff1a; DPDK downloadGetting Started Guide for Linux…
阅读更多...
业界数据架构的演变

业界数据架构的演变

目录 一、概述 二、业务处理-单体架构 三、业务处理-微服务架构 四、数据分析-大数据Lambda架构 五、数据分析-Kappa架构 六、数据分析-LambdaKappa混合架构 七、湖仓一体架构 一、概述 近年来随着越来越多的大数据技术被开源&#xff0c;例如&#xff1a;HDFS、Spark等…
阅读更多...
最小表示法

最小表示法

#define _CRT_SECURE_NO_WARNINGS #include<bits/stdc.h> using namespace std;const int N (int)3e5 5; int n; int a[N * 2];int main() {cin >> n;for (int i 0; i < n; i) {cin >> a[i];a[i n] a[i]; // 构造成链}int l 0, r 1; // 一开始 r …
阅读更多...
进入防火墙Web管理页面（eNSP USG6000V）和管理员模块

进入防火墙Web管理页面（eNSP USG6000V）和管理员模块

1、进入防火墙Web管理页面 USG系列是华为提供的一款高端防火墙产品&#xff0c;其特点在于提供强大的安全防护能力和灵活的扩展性。 以eNSP中的USG6000为例&#xff1a; MGMT口&#xff08;web管理口&#xff09;&#xff1a;对应设备上的G0/0/0口&#xff0c;上面初始配有一…
阅读更多...
算法-常见数据结构设计

算法-常见数据结构设计

文章目录 1. 带有setAll功能的哈希表2. LRU缓存结构3. O(1)时间插入删除随机(去重)4. O(1)时间插入删除随机(不去重)5. 快速获取数据流中的中位数6. 最大频率栈7. 全O(1)结构8. LFU缓存结构 本节的内容比较难, 大多是leetcodeHard难度级别的题目 1. 带有setAll功能的哈希表 哈希…
阅读更多...
最新文章

Copyright @ 2022~2023