A26399. 迷宫路径
填空题
困难
知识点
题目描述
迷宫路径
题目描述
给定 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
参考答案
#include<iostream>
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 < tail) {
int x = qx[head];
int y = qy[head];
head++;
for (int k = 0; k < 4; ++k) {
int nx = x + dx[k];
int ny = y + dy[k];
if (0 <= nx and nx < n and 0 <= ny and ny < 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 >> n >> m;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j) {
std::cin >> a[i][j];
}
bfs(0, 0);
std::cout << w[n-1][m-1] << "\n";
return 0;
}
上一题
下一题