1 条题解
-
0
#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
- 上传者