首页 › 题库 › C/C++编程考级 › C/C++编程六级 › 简答题
简答题 偏难
#12917

空间折叠

空间折叠

image3.png

image4.png

image5.png

image6.png

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; using pii = pair&lt;int, int&gt;; 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 &gt;&gt; H &gt;&gt; W;     int ch, cw, dh, dw;     cin &gt;&gt; ch &gt;&gt; cw &gt;&gt; dh &gt;&gt; dw;     // 输入下标1转0     int sx = ch - 1, sy = cw - 1;     int tx = dh - 1, ty = dw - 1;     for (int i = 0; i &lt; H; i++) cin &gt;&gt; grid[i];     memset(dist, 0x3f, sizeof dist);     dist[sx][sy] = 0;     deque&lt;pii&gt; 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 &amp;&amp; y == ty) break;         // 行动1:步行,代价0         for (auto &amp;d : dir4)         {             int nx = x + d[0], ny = y + d[1];             if (nx &lt; 0 || nx &gt;= H || ny &lt; 0 || ny &gt;= W) continue;             if (grid[nx][ny] == '#') continue;             if (dist[nx][ny] &gt; curCost)             {                 dist[nx][ny] = curCost;                 dq.emplace_front(nx, ny);             }         }         // 行动2:空间折叠,5*5范围,代价+1         for (int dr = -2; dr &lt;= 2; dr++)         {             for (int dc = -2; dc &lt;= 2; dc++)             {                 int nx = x + dr, ny = y + dc;                 if (nx &lt; 0 || nx &gt;= H || ny &lt; 0 || ny &gt;= W) continue;                 if (grid[nx][ny] == '#') continue;                 if (dist[nx][ny] &gt; curCost + 1)                 {                     dist[nx][ny] = curCost + 1;                     dq.emplace_back(nx, ny);                 }             }         }     }     int ans = dist[tx][ty];     cout &lt;&lt; (ans == INF ? -1 : ans) &lt;&lt; '\n';     return 0; }</pre>
这道题暂未补解析。