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

走迷宫 一个迷宫由R行C列格子组成,有的格子里有障碍物,不能走;有的格子是空地,可以走。 给定一个迷宫,求从左上角走到右下角最少需要走多少步(数据保证一定能走到…

走迷宫

一个迷宫由R行C列格子组成,有的格子里有障碍物,不能走;有的格子是空地,可以走。 给定一个迷宫,求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走,不能斜着走。

时间限制:1000

内存限制:65536

输入

第一行是两个整数,R和C,代表迷宫的长和宽。(1<= R,C <= 40) 接下来是R行,每行C个字符,代表整个迷宫。 空地格子用'.'表示,有障碍物的格子用'#'表示。 迷宫左上角和右下角都是'.'。

输出

输出从左上角走到右下角至少要经过多少步(即至少要经过多少个空地格子)。计算步数要包括起点和终点。

样例输入

5 5
..###
#....
#.#.#
#.#.#
#.#..

样例输出

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