1 条题解

  • 0
    @ 2026-2-17 22:40:17
    #include<bits/stdc++.h>
    using namespace std;
    
    // 棋盘最大尺寸,适配n,m≤2000的要求
    const int MAXN = 2005;
    // 无穷大常量,用于初始化最小向左次数数组
    const int INF = 0x3f3f3f3f;
    // 四个移动方向:上、下、左、右
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    
    char mp[MAXN][MAXN];    // 存储迷宫地图
    int min_a[MAXN][MAXN];  // min_a[i][j]:到达(i,j)的最少向左次数
    
    int main()
    {
        // 关闭cin同步,加速输入输出,应对大数据量
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    
        int n, m;
        // [1] 读取迷宫的行数n、列数m
        cin >> n >> m;
    
        int r, c;
        // [2] 读取起点坐标(r,c),题目为1-based索引
        cin >> r >> c;
    
        int x, y;
        // [3] 读取向左最大次数x、向右最大次数y
        cin >> x >> y;
    
        // [4] 读取n行迷宫地图,使用1-based索引
        for(int i = 1; i <= n; i++)
        {
            cin >> mp[i] + 1; // mp[i]+1 表示从第1列开始存储,适配1-based
        }
    
        // [5] 初始化最小向左次数数组为无穷大
        memset(min_a, 0x3f, sizeof(min_a));
        // 双端队列,存储格式:{当前向左次数, {行号, 列号}}
        deque<pair<int, pair<int, int>>> dq;
    
        // [6] 起点初始化:向左次数为0,加入队列
        min_a[r][c] = 0;
        dq.push_back({0, {r, c}});
    
        // [7] 0-1 BFS核心循环
        while(!dq.empty())
        {
            // 取出队首的当前状态
            auto cur = dq.front();
            dq.pop_front();
            int cur_a = cur.first;
            int i = cur.second.first;
            int j = cur.second.second;
    
            // 剪枝:如果当前状态的向左次数已经大于记录的最小值,直接跳过
            if(cur_a > min_a[i][j]) continue;
    
            // 遍历四个移动方向
            for(int k = 0; k < 4; k++)
            {
                int ni = i + dx[k];
                int nj = j + dy[k];
                // 合法性校验1:坐标在迷宫范围内,且目标格子可通行(不是障碍)
                if(ni < 1 || ni > n || nj < 1 || nj > m || mp[ni][nj] != '.')
                {
                    continue;
                }
    
                int new_a;
                // 计算新的向左次数
                if(k == 2) // 向左移动,向左次数+1
                {
                    new_a = cur_a + 1;
                }
                else // 上下、向右移动,向左次数不变
                {
                    new_a = cur_a;
                }
    
                // 合法性校验2:新的向左次数更优,才更新状态
                if(new_a < min_a[ni][nj])
                {
                    min_a[ni][nj] = new_a;
                    // 0代价(上下、向右)加入队首,1代价(向左)加入队尾,保证队列单调性
                    if(k == 2)
                    {
                        dq.push_back({new_a, {ni, nj}});
                    }
                    else
                    {
                        dq.push_front({new_a, {ni, nj}});
                    }
                }
            }
        }
    
        // [8] 统计所有可达的格子数量
        int ans = 0;
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                // 可达条件:
                // 1. 格子可通行;
                // 2. 到达的最小向左次数≤x;
                // 3. 对应的向右次数≤y
                if(mp[i][j] == '.' && min_a[i][j] <= x)
                {
                    long long b = (long long)(j - c) + min_a[i][j];
                    if(b >= 0 && b <= y)
                    {
                        ans++;
                    }
                }
            }
        }
    
        // [9] 输出最终结果
        cout << ans << '\n';
    
        return 0;
    }
    
    • 1

    信息

    ID
    1303
    时间
    1000ms
    内存
    256MiB
    难度
    2
    标签
    递交数
    1
    已通过
    1
    上传者