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

迷宫路径 题目描述 给定 n×m 个方格构成的图,每个格子都有一种地形: 有一些格子是墙,以符号 X 表示,墙不可通行。 有一些格子是空地,以符号 . 表示,空…

迷宫路径

题目描述

给定 n×m 个方格构成的图,每个格子都有一种地形:

有一些格子是墙,以符号 X 表示,墙不可通行。

有一些格子是空地,以符号 . 表示,空地可以通行。

请统计从左上角的方格出发,有多少种不同的路线可以以最短距离走到右下角。在行走过程中,不能进入地形为墙的方格,保证起点与终点方格地形不是墙。且行走时,只能移动到水平或垂直方向相邻的方格。

由于方案数可能很大,输出模 1,000,000,007 的余数。

输入格式

第一行:单个整数 n 与 m

第二行到第 n+1 行:第i+1 行每行有 m 个整数表示第 i 行的地形

输出格式

单个整数:表示路线方案模 1,000,000,007 的余数。


输入样例

3 3
...
.X.
...

输出样例

2

说明提示

30% 的数据,1≤n,m≤4

60% 的数据,1≤n,m≤10

100% 的数据,1≤n,m≤1000

限制

时间限制:1000ms

内存限制:512MiB

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include&lt;iostream&gt; char a[1000][1000]; int d[1000][1000]; int w[1000][1000]; int n, m; int qx[1000*1000]; int qy[1000*1000]; int dx[4] = {0, 1, 0, -1}; int dy[4] = {1, 0, -1, 0}; void bfs(int x, int y) {     qx[0] = x;     qy[0] = y;     d[x][y] = 1;     w[x][y] = 1;     int head = 0;     int tail = 1;     while (head &lt; tail) {         int x = qx[head];         int y = qy[head];         head++;         for (int k = 0; k &lt; 4; ++k) {             int nx = x + dx[k];             int ny = y + dy[k];             if (0 &lt;= nx and nx &lt; n and 0 &lt;= ny and ny &lt; m and a[nx][ny] == '.') {                 if (d[nx][ny] == 0) {                     d[nx][ny] = d[x][y] + 1;                     w[nx][ny] = w[x][y];                     qx[tail] = nx;                     qy[tail] = ny;                     tail++;                 }                 else if (d[nx][ny] == d[x][y] + 1) {                     w[nx][ny] += w[x][y];                     w[nx][ny] %= 1000000007;                 }             }         }     } } int main() {     std::cin &gt;&gt; n &gt;&gt; m;     for (int i = 0; i &lt; n; ++i)         for (int j = 0; j &lt; m; ++j) {             std::cin &gt;&gt; a[i][j];         }     bfs(0, 0);     std::cout &lt;&lt; w[n-1][m-1] &lt;&lt; "\n";     return 0; }</pre>
这道题暂未补解析。