简答题
偏难
#12917
空间折叠
空间折叠




答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#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;
}</pre>
这道题暂未补解析。