acgo题库
  • 首页
  • 题库
  • 学习
  • 天梯
  • 备赛

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
  • 资讯
  • 竞赛
  • 讨论
  • 团队
  • 商城
登录
注册
题目详情提交记录(0)
  • 题解

    #include<bits/stdc++.h> using namespace std; typedef long long ll; #define endl '\n' const int MAXN = 1005; const int INF = 1e9; char g[MAXN][MAXN]; int dist[MAXN][MAXN]; int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1}; int main(){ int h, w, ch, cw, dh, dw; scanf("%d%d%d%d%d%d", &h, &w, &ch, &cw, &dh, &dw); ch--; cw--; dh--; dw--; for(int i = 0; i < h; i++) scanf("%s", g[i]); for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) dist[i][j] = INF; deque<pair<int,int>> dq; dist[ch][cw] = 0; dq.push_front({ch, cw}); while(!dq.empty()){ auto [r, c] = dq.front(); dq.pop_front(); int d = dist[r][c]; if(r == dh && c == dw) break; // 步行 (代价 0): 入队头 for(int k = 0; k < 4; k++){ int nr = r + dr[k], nc = c + dc[k]; if(nr < 0 || nr >= h || nc < 0 || nc >= w) continue; if(g[nr][nc] == '#') continue; if(dist[nr][nc] > d){ dist[nr][nc] = d; dq.push_front({nr, nc}); } } // 魔法 (代价 1): 5×5 范围内所有道路格, 入队尾 for(int dr2 = -2; dr2 <= 2; dr2++){ for(int dc2 = -2; dc2 <= 2; dc2++){ if(dr2 == 0 && dc2 == 0) continue; int nr = r + dr2, nc = c + dc2; if(nr < 0 || nr >= h || nc < 0 || nc >= w) continue; if(g[nr][nc] == '#') continue; if(dist[nr][nc] > d + 1){ dist[nr][nc] = d + 1; dq.push_back({nr, nc}); } } } } printf("%d\n", dist[dh][dw] == INF ? -1 : dist[dh][dw]); return 0; }

    userId_undefined
    未知
    模拟·模拟练习生倔强青铜冒泡宗师→排序元老
    2阅读
    0回复
    0点赞
暂无数据

提交答案之后,这里将显示提交结果~

首页