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

走出迷宫 当你站在一个迷宫里的时候,往往会被错综复杂的道路弄得失去方向感,如果你能得到迷宫地图,事情就会变得非常简单。 假设你已经得到了一个n*m的迷宫的图纸,…

走出迷宫

当你站在一个迷宫里的时候,往往会被错综复杂的道路弄得失去方向感,如果你能得到迷宫地图,事情就会变得非常简单。

假设你已经得到了一个n*m的迷宫的图纸,请你找出从起点到出口的最短路。

时间限制:1000

内存限制:65536

输入

第一行是两个整数n和m(1<=n,m<=100),表示迷宫的行数和列数。 接下来n行,每行一个长为m的字符串,表示整个迷宫的布局。字符'.'表示空地,'#'表示墙,'S'表示起点,'T'表示出口。

输出

输出从起点到出口最少需要走的步数。

样例输入

3 3
S#T
.#.
...

样例输出

6
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; int n, m, p[10008], q[10008], ans[108][108], qx, qy, zx, zy; char a[108][108]; int xx[5] = {0, 1, -1, 0, 0}; int yy[5] = {0, 0, 0, 1, -1}; void bfs() {   a[qx][qy] = '#';   ans[qx][qy] = 0;   int head = 1;   int tail = 1;   p[1] = qx;   q[1] = qy;   while (head &lt;= tail) {     for (int i = 1; i &lt;= 4; i++) {       int h = p[head] + xx[i];       int l = q[head] + yy[i];       if (a[h][l] != '#' &amp;&amp; h &gt;= 1 &amp;&amp; l &gt;= 1 &amp;&amp; h &lt;= n &amp;&amp; l &lt;= m) {         a[h][l] = '#';         tail++;         p[tail] = h;         q[tail] = l;         ans[h][l] = ans[p[head]][q[head]] + 1;         if (h == zx &amp;&amp; l == zy) {           cout &lt;&lt; ans[h][l] &lt;&lt; endl;           return;         }       }     }     head++;   } } int main() {   cin &gt;&gt; n &gt;&gt; m;   for (int i = 1; i &lt;= n; i++) {     for (int j = 1; j &lt;= m; j++) {       cin &gt;&gt; a[i][j];       if (a[i][j] == 'S') {         qx = i;         qy = j;       }       if (a[i][j] == 'T') {         zx = i;         zy = j;       }     }   }   bfs();   return 0; }</pre>
这道题暂未补解析。