上海计算机学会2023年8月月赛C++丙组T5方格路径

方格路径

内存限制: 256 Mb时间限制: 1000 ms

题目描述

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

• 有一些格子是墙，以符号 # 表示，墙不可通行。
• 有一些格子是空地，以符号 . 表示，空地可以通行。

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

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

输入格式

• 第一行：单个整数 n 与 m
• 第二行到第 n+1 行：第 i+1 行每行有 m 个整数表示第 i 行的地形

输出格式

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

数据范围

• 30%的数据，1≤n,m≤4
• 60% 的数据，1≤n,m≤10
• 100% 的数据，1≤n,m≤1000

样例数据

输入:
3 3
...
.#.
...
输出:
2
 

解析：最短距离可以理解为只能向右或向下，一旦回头，就不是最短路径了。

可以用递推法，当前格的方案数为上方格方案数加左边格方案数。此代码可以得60分；

详见代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[1005][1005];
int dp[1005][1005];
int main() {
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
 
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            if (i==1&&j==1){//出发格方案为一
                dp[i][j]=1;
                continue;
            }
            if (a[i][j]=='#'){//不能通行
                dp[i][j]=0;
            }else{//可以通行，方案数为上加左
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
                dp[i][j]%=1000000007;
            }
        }
    }
    cout<<dp[n][m];
    return 0;
}

正解为BFS广度优先搜索，详见代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[1005][1005];//地图
int dp[1005][1005];//几种方案
int step[1005][1005];//到达该位置为第几步
int dx[4]={0,0,1,-1};//上下左右四个方向
int dy[4]={-1,1,0,0};
struct node{//每个点
    int x;
    int y;
};
queue <node> q;//广度优先搜索队列
int main() {
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    dp[1][1]=1;//初始位置方案数为1
    step[1][1]=1;//第一步
    node tmp;//初始化第一个位置
    tmp.x=1;tmp.y=1;
    q.push(tmp);//入队
    while(!q.empty()){//只要队列非空，继续搜索
        tmp=q.front();//取队首
        q.pop();
        int x=tmp.x;//出发点x坐标
        int y=tmp.y;//出发点y坐标
        for(int i=0;i<4;i++){//四个方向
            int xx=tmp.x+dx[i];//目标点x坐标
            int yy=tmp.y+dy[i];//目标点y坐标
            //如果目标点出界或者为墙
            if (xx>n||xx<1||yy>m||yy<1||a[xx][yy]=='#'){
                continue;//去下一个目标点
            }
            if (step[xx][yy]==0){//如果是首次到达
                dp[xx][yy]=dp[x][y];//方案数同出发点
                step[xx][yy]=step[x][y]+1;//步数为出发点加一
                node now;//目标点入队
                now.x=xx;
                now.y=yy;
                q.push(now);
            //如果非首次到达且步数同首次到达相同
            }else if(step[xx][yy]==step[x][y]+1){
                dp[xx][yy]+=dp[x][y];//方案数增加出发点方案数
                dp[xx][yy]%=1000000007;//方案数取模
            }//其他情况都不用处理
        }
    }
    cout<<dp[n][m];//最后终点坐标的方案数即为答案
    return 0;
}