A18277. 空间折叠
填空题
困难
知识点
题目描述
空间折叠
题目描述
在古老的星尘遗迹中，地面被划分为 H 行 W 列的石板网格。
每块石板要么是完好的（用.表示），要么是破碎的（用#表示），只有完好石板才能安全站立。
你从入口 (Ch,Cw) 出发，要前往祭坛 (Dh,Dw)。
入口和祭坛保证是完好石板，且位置不同。
你可以执行以下两种行动：
步行：向上、下、左、右移动到相邻的完好石板。该行动不消耗能量。
空间折叠：以当前石板为中心，向 (5times5) 的方形区域（即行偏移 -2 到 +2，列偏移 -2 到 +2）内的任意完好石板瞬间传送。该行动消耗 1 点能量，且落点不能超出遗迹边界。
求从入口到祭坛所需的最少能量消耗，无法到达则输出 (-1)。
输入格式
第一行：两个整数 (H, W)
第二行：两个整数 ((Ch,Cw)（入口坐标）
第三行：两个整数 (Dh,Dw)（祭坛坐标）
接下来 H 行：每行一个长度为 W 的字符串，‘.’ 代表通路，‘#’ 代表障碍
输出格式输出最少消耗的能量数值；不可达输出 -1
输入样例 1
4 4
1 1
4 4
..#.
..#.
.#..
.#..输出样例1
1输入样例 2
4 4
1 4
4 1
.##.
####
####
.##.输出样例2
-1输入样例 3
4 4
2 2
3 3
....
....
....
....输出样例3
0输入样例 4
4 5
1 2
2 5
#.###
####.
#..##
#..##输出样例4
2参考答案
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAXN = 1005;
const int INF = 0x3f3f3f3f;
int H, W;
char grid[MAXN][MAXN];
int dist[MAXN][MAXN];
// 普通四方向步行偏移
int dir4[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> H >> W;
int ch, cw, dh, dw;
cin >> ch >> cw >> dh >> dw;
// 输入下标1转0
int sx = ch - 1, sy = cw - 1;
int tx = dh - 1, ty = dw - 1;
for (int i = 0; i < H; i++) cin >> grid[i];
memset(dist, 0x3f, sizeof dist);
dist[sx][sy] = 0;
deque<pii> dq;
dq.emplace_back(sx, sy);
while (!dq.empty())
{
auto [x, y] = dq.front();
dq.pop_front();
int curCost = dist[x][y];
// 到达终点直接提前输出答案
if (x == tx && y == ty) break;
// 行动1：步行，代价0
for (auto &d : dir4)
{
int nx = x + d[0], ny = y + d[1];
if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
if (grid[nx][ny] == '#') continue;
if (dist[nx][ny] > curCost)
{
dist[nx][ny] = curCost;
dq.emplace_front(nx, ny);
}
}
// 行动2：空间折叠，5*5范围，代价+1
for (int dr = -2; dr <= 2; dr++)
{
for (int dc = -2; dc <= 2; dc++)
{
int nx = x + dr, ny = y + dc;
if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
if (grid[nx][ny] == '#') continue;
if (dist[nx][ny] > curCost + 1)
{
dist[nx][ny] = curCost + 1;
dq.emplace_back(nx, ny);
}
}
}
}
int ans = dist[tx][ty];
cout << (ans == INF ? -1 : ans) << '\n';
return 0;
}
上一题
下一题