面对新手向的暴力过题技巧-cpp

njtc-算竞队-yxy

写在前面

• 在一些类似于迷宫问题、走格子、最短路、最长路、寻路问题、树上寻宝问题等 通常会采用bfs、dfs、dp等方法。我利用一些题型来简单的使用一下过题的思想。

介绍

• tips：以下解释来自deepseek

• 当我们想在诸如树或图这类复杂数据结构中寻找特定信息时，BFS（广度优先搜索）和DFS（深度优先搜索）是两种最基础且重要的搜索策略。它们的核心区别在于访问节点的顺序。

  想象一下你身处一个巨大的迷宫：

  • BFS（广度优先搜索） 就像是一支训练有素的军队，会逐层推进。它从起点开始，首先访问所有一步就能到达的地方，然后再去访问从这些地方出发两步能到达的所有新地方，以此类推。这种方式确保了你找到的路径一定是最短路径。它通常借助一个队列（Queue）来实现“先来先服务”的顺序。

  • DFS（深度优先搜索） 则像一个执着探险家，会一条路走到黑。它从起点选择一条岔路一直走下去，直到尽头，然后退回上一个岔口，尝试另一条没走过的路。这种方式优先探索的是图的“深度”，它可能会很快地进入深层分支，但找到的路径不一定是最短的。它通常借助一个栈（Stack）来实现，或者直接使用函数的递归调用来模拟这个“回溯”的过程。

  简单总结一下：

  • BFS：广度优先，层层扫荡，找到的是最短路径。

  • DFS：深度优先，勇往直前，回溯另寻他路。

  选择使用哪种算法取决于你的需求：如果需要最短路径或最近的结果（比如社交网络中的好友关系），BFS更合适；如果需要遍历所有可能（比如排列组合、穷举所有方案），或者树结构非常深而宽，DFS往往是更好的选择。

相关题目

迷宫问题(经典)

原题链接来自：(njtc-oj平台)xfxcy https://xfxcy.com/p/P0230

• 题目描述：迷宫由一个网格组成，每个单元格要么是路径（用 0 表示），要么是无法通过的墙壁（用 1 表示）。小飞侠从迷宫的左上角开始（坐标为 ( 1 , 1 ) (1,1)），目标是到达迷宫的右下角（坐标为 ( n , m ) (n,m)）。 在迷宫中，小飞侠可以向上、向下、向左或向右移动。
• 输入格式：第一行包含两个整数 n n 和 m m。 接下来 n n 行，每行包含 m m 个整数（ 0 0 或 1 1），表示完整的二维数组迷宫；
• 输出格式：输出一个整数，表示从左上角移动至右下角的最少移动次数；
• 数据范围：1≤n≤1000.   1≤m≤1000.   1≤m≤1000.

考虑到时间复杂度 本题无法使用dfs，所以使用bfs解决。

参考代码(bfs)：

非特殊情况不推荐使用万能头，会拖慢整体的编译速度。

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <unordered_map>
#include <map>
#include <cstring>
#include <cmath>
#include <unordered_set>
#include <set>
#include <utility>
#include <climits>
#include <iomanip>
#include <stack>
#include <bitset>

#define int long long
#define PII pair<int, int> 
#define TLLL tuple<int , int , int>
#define INF 0x3f3f3f3f3f3f3f3f
#define all(v) v.begin() + 1 , v.end()
#define ALL(v) v.begin() , v.end()
#define endl "\n"
using namespace std;

const int N = 1e3 + 10;
int n , m;
int g[N][N] , dist[N][N];
bool st[N][N];

int dx[] = {0 , 1 , 0 , -1} , dy[] = {1 , 0 , -1 , 0};  //四个方向

void bfs(int sx , int sy)
{
    queue<PII> q;
    q.push({sx , sy});
    st[sx][sy] = true;

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        int x = t.first , y = t.second;

        for (int i = 0 ; i < 4 ; i ++ )
        {
            int xx = dx[i] + x , yy = dy[i] + y;

            if (xx < 1 || xx > n || yy < 1 || yy > m || g[xx][yy]) continue;
            if (st[xx][yy]) continue;

            st[xx][yy] = true;
            dist[xx][yy] = dist[x][y] + 1;
            q.push({xx , yy});
            
            if (xx == n && yy == m) return ;
        }
    }
}

void solve() 
{   
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i ++ ) 
        for (int j = 1 ; j <= m ; j ++ )
            cin >> g[i][j];
    
    bfs(1 , 1);

    cout << dist[n][m] << endl;

    return ;
}

signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T = 1;
    while (T -- ) solve();
    return 0;
}

 

额外的，可以使用dijkstra(无负权边的情况下)   对！没错，就是离散数学里你学过的东西！

• 解释：

  Dijkstra算法是一种非常著名且高效的算法，用于在带权图中寻找从一个起始点到所有其他点的最短路径。这里的“权”通常代表了距离、成本、时间等可量化的度量。

  它与BFS的核心区别在于“权”。BFS认为每走一步的成本都是相同的（可以看作权值为1），它通过“层数”来计算最短距离。而Dijkstra算法处理的是权值各不相同的图，某些路径可能边数多但总成本低，某些可能边数少但总成本高。

  它的核心思想可以用一个比喻来理解：

  想象你是一位城市交通指挥官，目标是计算从市中心（起始点）到城市中所有其他地点的最短行车时间。

  1. 初始化：你首先标记市中心的时间为0，而所有其他地点的时间暂时标记为“无穷大”，表示你还不知道如何到达那里。

  2. 贪心选择：你从当前已知可达的、且尚未被最终确认的地点中，选出离市中心最近的那个（也就是当前耗时最短的地点）。你确信，对于这个地点，你已经找到了绝对最短的路径。因为如果存在一条更短的路径，那它必然要经过一个耗时更长的其他地点，这显然是不可能的（前提是所有权重不能为负数）。

  3. 扩散更新：基于这个刚被确认的地点，你去查看从它出发的所有道路。你计算：“从市中心到这里的时间” + “从这里到下一个路口的时间”。如果这个总时间比之前记录的到达那个路口的时间更短，你就更新那个路口的记录。

  4. 重复：你不断地重复第2和第3步：从所有已知但未确认的地点中选出耗时最短的，确认它，然后更新它的邻居。直到所有地点都被确认，或者你找到了到目标地点的最短路径。

参考代码(dijkstra)：

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <unordered_map>
#include <map>
#include <cstring>
#include <cmath>
#include <unordered_set>
#include <set>
#include <utility>
#include <climits>
#include <iomanip>
#include <stack>
#include <bitset>

#define int long long
#define PII pair<int, int> 
#define TLLL tuple<int , int , int>
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f
#define all(v) v.begin() + 1 , v.end()
#define ALL(v) v.begin() , v.end()
#define endl "\n"
using namespace std;

const int N = 4e6 + 10;
int e[N] , ne[N] , h[N] , idx , dist[N];
bool st[N];

//链式前向星存图，相关概念可以参考过往文章->图论基础-透析链式前向星
inline void add(int a , int b)
{
    e[idx] = b , ne[idx] = h[a] , h[a] = idx ++;
}

//将二维坐标转化为一维（即：从上到下，从左到右，依次编号为1,2,3,...,n * m）。
inline int transIndex(int a , int b , int m)
{
    return (a - 1) * m + b;
}

//dijkstra
void dijkstra()
{
    memset(st , false , sizeof st);
    memset(dist , inf , sizeof dist);

    priority_queue<PII , vector<PII> , greater<PII> > heap;
    heap.push({0 , 1});

    dist[1] = 0;
    st[1] = true;

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int distance = t.first , index = t.second;

        for (int i = h[index] ; ~i ; i = ne[i])
        {
            int j = e[i];

            if (dist[j] > distance + 1)
            {
                dist[j] = distance + 1;
                heap.push({ dist[j] , j});
            }
        }
    }

    return ;
}

//函数本体
void solve()
{
    int n , m;
    cin >> n >> m;
    vector<vector<int> > g(n + 1 , vector<int>(m + 1));
    for (int i = 1 ; i <= n ; i ++ )
        for (int j = 1 ; j <= m ; j ++ )
            cin >> g[i][j];
    
    memset(h , -1 , sizeof h);
    int dx[] = {0 , 1 , 0 , -1} , dy[] = {1 , 0 , -1 , 0};  //四个方向

//坐标转换
    for (int i = 1 ; i <= n ; i ++ )
    {
        for (int j = 1 ; j <= m ; j ++ )
        {
            if (g[i][j]) continue;

            int u = transIndex(i , j , m);

            for (int k = 0 ; k < 4 ; k ++ )
            {
                int x = i + dx[k] , y = j + dy[k];

                if (x < 1 || x > n || y < 1 || y > m || g[x][y]) continue;
                
                int v = transIndex(x , y , m);
                add(u , v) , add(v , u);  //题目描述可以上下左右，即 双向图
            }
        }
    }

    dijkstra();
    int end = transIndex(n , m , m);

    cout << dist[end] << endl;

    return ;
}

signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T = 1;
    // cin >> T;
    while (T -- ) solve();
    return 0;
}

 

持续更新中...