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

news/2024/7/18 7:40:20 标签: 笔记

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.niftyadmin.cn/n/5544143.html

相关文章

C语言2 常量

C语言2 常量

目录 1. 整型常量 2. 浮点常量 3. 字符串常量 4. 标识常量 5. 字符常量 C语言中&#xff0c;常量是指在程序运行期间其值不发生变化的数据。常量可以分为整型常量、浮点常量、字符串常量和标识常量。 1. 整型常量 整型常量&#xff08;简称整数&#xff09;表示整数值&a…
阅读更多...
提升内容分享类营销效果的秘籍大公开

提升内容分享类营销效果的秘籍大公开

今天有丰富实战经验的“蚓链数字化营销平台”来给大家分享一些能有效提高内容分享类数字化营销方案中用户的参与度和转化率的方法。 创造有价值且引人入胜的内容 一定要让分享的内容实用、有趣或者独特&#xff0c;满足大家的需求和兴趣。多运用生动的故事、案例和数据来支持观…
阅读更多...
Perl 语言开发（九）：深入探索Perl语言的文件处理

Perl 语言开发（九）：深入探索Perl语言的文件处理

目录 1. 文件打开与关闭 1.1 打开文件 1.2 关闭文件 2. 读取文件内容 2.1 逐行读取 2.2 一次性读取整个文件 3. 写入文件内容 3.1 覆盖写入 3.2 追加写入 4. 文件测试操作 4.1 文件测试运算符 5. 文件路径操作 5.1 文件路径处理模块 5.2 获取文件路径信息 6. 文…
阅读更多...
比Elasticsearch更高效的开源搜索引擎Meilisearch——筑梦之路

比Elasticsearch更高效的开源搜索引擎Meilisearch——筑梦之路

功能说明 快速与高效&#xff1a; Meilisearch 旨在提供快速的搜索速度。它可以在毫秒级别内返回查询结果&#xff0c;即使在处理大型数据集时也是如此。 例如&#xff0c;在官方提供的基准测试中&#xff0c;使用 Meilisearch 处理 10 万个文档时&#xff0c;平均搜索时间为 …
阅读更多...
VPN 的入门介绍

VPN 的入门介绍

VPN&#xff08;虚拟专用网络&#xff09; 简介 虚拟专用网络&#xff0c;简称虚拟专网&#xff08;VPN&#xff09;&#xff0c;其主要功能是在公用网络上建立专用网络&#xff0c;进行加密通讯。在企业网络中有广泛应用。VPN网关通过对数据包的加密和数据包目标地址的转换实…
阅读更多...
JavaSE第10篇：常用类

JavaSE第10篇：常用类

文章目录 一、Object1、Object使用2、toString3、equals和4、hashCode5、clone6、finalize7、getClass8、wait、notify和notifyAll 二、使用步骤 一、Object 1、Object使用 Object类是所有Java的根父类 如果在类的声明中未使用extends关键字指明其父类&#xff0c;则默认父类…
阅读更多...
【笔试常见编程题06】最近公共祖先、求最大连续bit数、二进制插入、查找组成一个偶数最接近的两个素数

【笔试常见编程题06】最近公共祖先、求最大连续bit数、二进制插入、查找组成一个偶数最接近的两个素数

1. 最近公共祖先 将一棵无穷大满二叉树的结点按根结点一层一层地从左往右编号&#xff0c;根结点编号为1。现给定a&#xff0c;b为两个结点。设计一个算法&#xff0c;返回a、b最近的公共祖先的编号。注意其祖先也可能是结点本身。 测试样例&#xff1a; 2&#xff0c;3 返回&a…
阅读更多...
支付宝沙箱对接（GO语言）

支付宝沙箱对接（GO语言）

支付宝沙箱对接 1.1 官网1.2 秘钥生成&#xff08;系统默认&#xff09;1.3 秘钥生成&#xff08;软件生成&#xff09;1.4 golan 安装 SDK1.5 GoLand 代码1.6 前端代码 1.1 官网 沙箱官网: https://open.alipay.com/develop/sandbox/app 秘钥用具下载&#xff1a; https://ope…
阅读更多...
最新文章

Copyright @ 2022~2023