洛谷P11228地图探险题解(CSP-J 2024真题)

贾蔷
• 阅读 79

洛谷P11228地图探险题解(CSP-J 2024真题) 一、题目重述 给定n×m的二维矩阵表示探险地图,每个格子可能是: 平地('.') 障碍物('#') 起点('S') 终点('E') 求从起点到终点的最短路径步数,无法到达则输出-1。 二、核心算法:BFS广度优先搜索 选择原因:BFS是解决无权图最短路径问题的最优方案,时间复杂度O(nm)完全适合题目约束条件(典型n,m≤1000)

二、完整C++实现(带详细注释)

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

const int N = 1005;
char grid[N][N];
int dist[N][N]; // 距离矩阵
int n, m;
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; // 方向数组

int bfs(int sx, int sy, int ex, int ey) {
    memset(dist, -1, sizeof dist);
    queue<pair<int,int>> q;
    q.push({sx, sy});
    dist[sx][sy] = 0;

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            // 越界检查 || 障碍物检查 || 已访问检查
            if (nx < 0 || nx >= n || ny < 0 || ny >= m 
                || grid[nx][ny] == '#' || dist[nx][ny] != -1) 
                continue;

            dist[nx][ny] = dist[x][y] + 1;
            if (nx == ex && ny == ey) return dist[nx][ny];
            q.push({nx, ny});
        }
    }
    return -1;
}

int main() {
    cin >> n >> m;
    int sx, sy, ex, ey;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
            if (grid[i][j] == 'S') sx = i, sy = j;
            if (grid[i][j] == 'E') ex = i, ey = j;
        }

    cout << bfs(sx, sy, ex, ey);
    return 0;
}

四、算法优化点 双向BFS:当起点和终点都已知时,可减少50%搜索范围 A*算法:若有启发式信息可用(如坐标距离) 输入优化:使用快速IO方法处理大规模数据

原文:洛谷P11228地图探险题解(CSP-J 2024真题)

点赞
收藏
评论区
推荐文章
Stella981 Stella981
3年前
HDU 3416 Marriage Match IV (Dijkstra+最大流)
题意:N个点M条边的有向图,给定起点S和终点T,求每条边都不重复的ST的最短路有多少条。分析:首先第一步需要找出所有可能最短路上的边。怎么高效地求出呢?可以这样:先对起点S,跑出最短路;对于每条边e(u,v,w),若d\u\wd\v\。那么e就是最短路上的一条边。在前向星存储的图中遍历即可。网上还有题解用的方法是分别从S和T跑两
Stella981 Stella981
3年前
FZU2150 Fire Game
题目:_两个熊孩子在n\m的平地上放火玩,表示草,两个熊孩子分别选一个格子点火,火可以向上向下向左向右在有草的格子蔓延,点火的地方时间为0,蔓延至下一格的时间依次加一。求烧完所有的草需要的最少时间。如不能烧完输出1。_输入:_第一行,输入一个T,表示有T组测试数据。每组数据由一个n,m分别表示行列_1
Stella981 Stella981
3年前
AStar寻路1
A星算法是一种启发式的搜索方法,通过一个路径评估函数,来动态确定最佳路径。这点和广度搜索不同。基本思想是有2个列表,open和close,open列表里面的节点表示待搜索周围点的节点,close列表里面记录着不需要搜索的节点。启发式函数fgh;f表示该路径的代价,g表示起点到搜索的点的该条路径的实际值,h表示该搜索的点到终点的估计值。h的
贾蔷 贾蔷
5天前
2023年GESP六级小杨握手问题(洛谷B3874):Fenwick树求解逆序对的代码解析
一、题目解读“小杨的握手问题”源自2023年GESP六级考试(对应洛谷题目B3874)。题目描述为:给定一个长度为N的排列,每次将当前数与之前未访问过的数握手,求总共握手次数。本质上是求排列中逆序对的个数,即统计每个数右侧比它小的元素数量。需设计高效算法在
深度学习 深度学习
5天前
【CSP-S 2019】括号树(洛谷P5658):栈+DFS
一、题目解读括号树问题(洛谷P5658)要求处理一个由括号序列转化的树结构:每个节点表示一个括号,'('为子节点,')'为父节点。题目给定一棵n个节点的树,需计算每个节点的深度(括号层数),并输出所有节点深度与节点编号乘积的异或和。核心在于将括号序列转化为
贾蔷 贾蔷
5天前
牛客13279题解:利用递归与深度优先搜索计算树的最大高度(附完整代码)
一、题目解读牛客13279题要求计算给定树的最大高度。题目输入一棵以邻接表形式表示的树(节点从0开始编号),需要输出从根节点到最深叶节点的最长路径长度。树的结构由n个节点和n1条边构成,保证为连通无环图。理解题目核心在于准确获取树的拓扑关系,并设计算法遍历
贾蔷 贾蔷
5天前
2023年GESP六级题解:洛谷P10108闯关游戏动态规划解法详解
一、题目解读本文针对2023年GESP六级题目“闯关游戏”(洛谷P10108)进行详细解析。题目要求玩家通过不同关卡路径选择,计算从起点到终点的最大得分。关卡间存在跳跃规则,需结合动态规划思想设计高效算法,最终输出最优得分。二、解题思路采用动态规划(Dyn
深度学习 深度学习
4天前
2024年蓝桥杯国赛A组题 九宫格全解析:基于BFS算法的代码实现与优化
2024年蓝桥杯国赛A组题九宫格全解析:基于BFS算法的代码实现与优化蓝桥杯国赛九宫格问题BFS算法代码解析解题步骤第1张一、题目解读2024年蓝桥杯国A的九宫格题目(对应洛谷P10578)要求通过旋转九宫格中的2x2区域,实现从初始状态到目标状态的转换,
贾蔷 贾蔷
4星期前
NOIP 2000 提高组 洛谷1004题(方格取数)解题思路与C++代码解析
一、题目描述简要描述题目:例如,在一个n×n的方格图中,每个格子包含一个正整数。需要选择两条从左上角到右下角的路径,路径可重复经过格子,但两条路径除起点和终点外不能相交。求两条路径数字和的最大值。二、解题思路与算法分析1.问题分析1.问题核心是求解两条不交
贾蔷 贾蔷
5天前
牛客12576题全解析:动态规划+质因数分解解决跳跃问题
一、题目解读牛客12576题是一道经典的算法题,要求给定起点N和终点M,求解从N到M的最少跳跃次数。题目考察的核心在于路径优化与动态规划思想,需结合数论中的质因数分解技巧,通过合理设计算法降低时间复杂度,避免暴力枚举的指数级耗时。二、解题思路采用“动态规划