当前位置：首页 > 入门组 > 「CSP-J 2024真题精讲」洛谷P11228地图探险：递归算法的精妙应用附完整C++实现

「CSP-J 2024真题精讲」洛谷P11228地图探险：递归算法的精妙应用附完整C++实现

5天前

一、题目解读

2024年CSP-J认证考试中的地图探险题要求选手实现一个探索算法：

核心需求：在n×m矩阵中，从起点出发按特定方向规则探索可达区域
关键参数：步数限制k、初始方向d、移动规则（右→下→左→上循环）
输出目标：统计有效探索的独特格子数量
算法亮点：递归实现方向切换与步数控制的完美结合

二、解题思路分析

递归设计逻辑

基线条件：剩余步数k归零时终止
方向处理：0~3分别对应右/下/左/上移动
路径标记：flag矩阵记录已访问格子

关键创新点

方向切换机制：遇障碍时d = (d + 1) % 4实现循环转向
剪枝优化：通过flag矩阵避免重复计数

三、解题步骤分解

输入阶段

处理多组测试数据（T组）
读取矩阵尺寸n,m和步数限制k

初始化阶段

清空flag矩阵（memset快速初始化）
记录起点坐标(sx,sy)和初始方向d

递归探索阶段// 核心递归逻辑： if (可移动){ 如果是新格子则增加计数消耗步数k并继续当前方向移动 }else{ 转向并消耗步数k 保持原位重新尝试 }

四、完整代码实现（带注释）

#include<iostream>
using namespace std;
int n, m, k;
int flag[1001][1001] = {0}; // 访问标记矩阵
int ret = 1; // 结果计数器（起点默认已访问）

void explore(string s[],int x,int y,int d) {
    if (k==0)return; // 终止条件：步数耗尽
    int x1, y1;
    // 方向处理：0右 1下 2左 3上
    if (d == 0)(x1 = x), (y1 = y + 1);
    else if (d == 1)(x1 = x + 1), (y1 = y);
    else if (d == 2)(x1 = x), (y1 = y - 1);
    else (x1 = x - 1), (y1 = y - 1);
    
    if ((x1 < n and x1>=0) and (y1 < m and y1>=0)and s[x1][y1] == '.') {
        if (flag[x1][y1]==0){ // 新格子计数
            flag[x1][y1] = 1;
            ret++;
        }
        k--;
        explore(s, x1, y1, d); // 保持方向前进
    }else {
        d = (d + 1) % 4; // 转向处理
        k--;
        explore(s, x, y, d); // 原位转向
    }
}

int main() {
    int T; cin >> T; // 测试用例数
    for (int i = 0;i < T;i++) {
        ret = 1; // 重置计数器（起点计入）
        cin >> n >> m >> k;
        // 初始化标记矩阵
        for(int i=0;i<n;i++) memset(flag[i], 0, m);
        int sx, sy, d;
        cin >> sx >> sy >> d;
        string s[1001];
        for (int i = 0;i < n;i++) cin >> s[i]; // 读入地图
        
        flag[sx-1][sy-1] = 1; // 标记起点
        explore(s, sx-1, sy-1, d);
        cout << ret<<endl;
    }
    return 0;
}