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

迷宫问题(2024-3-7级) 定义一个二维数组: int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0,…

迷宫问题(2024-3-7级)

定义一个二维数组:

int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,

};

它表示一个迷宫, 其中的 1 表示墙壁, 0 表示可以走的路, 只能横着走或竖着走, 不能斜着走, 要求编程序找出从左上角到右下角的最短路线。

时间限制: 1000

内存限制: 65536

输入

一个 5 × 5 的二维数组, 表示一个迷宫。 数据保证有唯一解。

输出

左上角到右下角的最短路径, 格式如样例所示。


样例输入

0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

样例输出

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">/*#include &lt;iostream&gt;*/ #include &lt;bits/stdc++.h&gt; using namespace std; const int idata = 50 + 5; int maps[idata][idata]; bool judge[idata][idata]; int change[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int nx, ny; int x[idata], y[idata]; int show[30]; bool flag; void print(int tail) {   if (show[tail])     print(show[tail]);   cout &lt;&lt; "(" &lt;&lt; x[tail] &lt;&lt; ", " &lt;&lt; y[tail] &lt;&lt; ")" &lt;&lt; endl; } int main() {   int head, tail;   register int i, j;   for (i = 0; i &lt; 5; i++) {     for (j = 0; j &lt; 5; j++) {       cin &gt;&gt; maps[i][j];       if (maps[i][j] == 1)         judge[i][j] = 1;     }   }   head = 0;   tail = 1;   judge[0][0] = 1;   show[tail] = head;   while (tail &gt; head) {     head++;     for (i = 0; i &lt; 4; i++) {       nx = x[head] + change[i][0];       ny = y[head] + change[i][1];       if (nx &gt;= 0 &amp;&amp; nx &lt; 5 &amp;&amp; ny &gt;= 0 &amp;&amp; ny &lt; 5 &amp;&amp; !judge[nx][ny]) {         tail++;         x[tail] = nx;         y[tail] = ny;         judge[nx][ny] = 1;         show[tail] = head;         if (nx == 4 &amp;&amp; ny == 4) {           flag = 1;           print(tail);           break;         }       }     }     if (flag)       break;   }   return 0; }</pre><p></p>
这道题暂未补解析。