第2题

给定 $n\times m$ 个方格构成的图，每个格子都有一种地形：有一些格子是墙，以符号 # 表示，墙不可通行；有一些格子是空地，以符号 . 表示，空地可以通行。请统计从左上角的方格出发，有多少种不同的路线可以以最短距离走到右下角。在行走过程中，不能进入地形为墙的方格，保证起点与终点方格地形不是墙。且行走时，只能移动到水平或垂直方向相邻的方格。由于方案数可能很大，输出模 $1000000007$ 的余数。

#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 ( ____(1)____ ) {
                    d[nx][ny] = ____(2)____;
                    w[nx][ny] = ____(3)____;
                    qx[tail] = nx;
                    qy[tail] = ny;
                    tail++;
                }
                else if (____(4)____) {
                    w[nx][ny] = ____(5)____;
                    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 << ____(6)____ << "\n";
}

(6) 处应填（ ）。

{{ select(1) }}

• d[n-1][m-1]
• d[n][m]
• w[n-1][m-1]
• w[n][m]