2020 蓝桥杯大学模拟赛(三) - 程序设计：突破障碍题解

蔚落 2022-12-28 14:15 115阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入描述
     *  输出描述
     *  数据范围
     *  样例输入
     *  样例输出
 *  算法分析
 *  解题代码

--------------------

# 题目描述 #

⼩明有⼀个 `n * m` 的⼆维迷宫，在样例中给出。其中 ‘\#’ 表示障碍物, ‘S’ 表示起点, ‘T’ 表示 终点, ‘.’ 表示空地。保证起点和终点都是空地。每次移动可以从当前所在空地移动到相邻的空地, 只能往上下左右四个⽅向⾛。

现在他想知道，从起点到终点最少经过⼏个障碍物。

## 输入描述 ##

> 第⼀⾏两个整数`n, m` ，意义如题所示  
> 接下来 `n` ⾏每⾏ `m`个字符，表示整张地图

## 输出描述 ##

> 输出⼀⾏⼀个整数表示最少经过⼏个障碍物

## 数据范围 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]

## 样例输入 ##

5 5
    S....
    ####.
    .###.
    .####
    ....T

## 样例输出 ##

# 算法分析 #

看到这道题的第一想法：广搜！搜到终点T看最短路

但很快这种想法就被推翻了

例如：

2 5
    S###T
    .....

在这种情况下，最短路的障碍代价不如远路来的少。

**那怎么办？**

还有一种办法，就是dfs深搜骗分

**接下来是满分答案**

因此我们要思考一下我们搜索的条件

常规的bfs搜索而言，我们评判的标准是路程最短，也就是代价最短。

**那么对于这道题，我们就考虑在什么情况下能够得到的代价最小？**

很明显可以看出，由 `.` 这种情况下扩展出来的代价会比由 `#` 得到的代价更小，因此我们先对 `.` 这种情况下得出的代价情况去扩展其他的点。

也就是我们对于迷宫中每一个点都用一个数据结构 f\[MAXN\]\[MAXN\] 来记录到当前点的最小代价。

**那么对于这种情况我们可以用双端队列，对于这种代价的优先级，分开插入。**

**当遇到 `.` 这种情况时，就将这种情况插入到队列的前端优先处理**

**当遇到 `#` 这种情况时，就将这种情况插入到队列的尾部后处理**

# 解题代码 #

#include <iostream>
    #include <queue>
    using namespace std;
    
    int n,m;
    char mp[305][305];  //记录迷宫
    int f[305][305];    //记录到每个点最小的代价
    int vis[305][305];  //记录每个点是否已走过
    typedef pair<int, int> ii;
    ii sn,tn;
    int dx[4] = {
        1, 0, -1, 0};
    int dy[4] = {
        0, 1, 0, -1};
    
    void bfs()
    {
        
        deque<ii> q;
        q.push_back(sn);
        vis[sn.first][sn.second] = 1;
        
        while(!q.empty()){
        
            ii now = q.front();
            q.pop_front();
            
            for(int i = 0; i < 4; i++){
        
                ii next;
                next.first = now.first + dx[i];
                next.second = now.second + dy[i];
                
                if(next.first < 1 || next.first > n || next.second < 1 || next.second > n) continue;
                if(vis[next.first][next.second]) continue;
                
                //如果下一个节点是墙，那么这种情况下拓展到最小的可能性较小，应该后进行扩展
                //因此将他插入到队列的后端
                if(mp[next.first][next.second] == '#'){
        
                    q.push_back(next);
                    f[next.first][next.second] = f[now.first][now.second] + 1;
                }
                //如果下一个节点不是墙，那么这种情况下拓展到最小的可能性较大，应该先进行扩展
                //因此将他插入到队列的前端
                else{
        
                    q.push_front(next);
                    f[next.first][next.second] = f[now.first][now.second];
                }
                
                vis[next.first][next.second] = 1;
            }
            
        }
    }
    
    int main()
    {
        
        cin >> n >> m;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++){
        
                cin >> mp[i][j];
                if(mp[i][j] == 'S'){
        
                    sn.first = i;
                    sn.second = j;
                }
                if(mp[i][j] == 'T'){
        
                    tn.first = i;
                    tn.second = j;
                }
            }
        
        bfs();
        
        cout << f[tn.first][tn.second] << endl;
        
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]: /images/20221120/90fbbce973d8462d8cb5b6478550a8c2.png