2020 蓝桥杯大学模拟赛(二) - 结果填空：迷宫题解

电玩女神 2022-12-28 14:15 118阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入
 *  算法分析
 *   *  方法一：
     *   *  如何解决并发性问题呢？
     *  方法二：
     *   *  如何解决并发性问题呢？
     *  代码（方法一）（未过，后续修正）
     *  代码（方法二）

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

# 题目描述 #

下图给出了⼀个迷宫的平⾯图，其中标记为 1 的为障碍，标记为 0 的为可以通⾏的地⽅。

010000
    000100
    001001
    110000

迷宫的⼊⼝为左上⻆，出⼝为右下⻆，在迷宫中，只能从⼀个位置⾛到这个它的上、下、左、 右四个⽅向之⼀。

对于上⾯的迷宫，从⼊⼝开始，可以按 DRRURRDDDR 的顺序通过迷宫，⼀共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右⾛。

对于下⾯这个迷宫（ 30 ⾏ 50 列），我们可以最上⽅⼀⾏的任意⼀个格⼦作为⼊⼝；以最下⽅ ⼀⾏的任意⼀个格⼦作为出⼝。请找出通过迷宫步数最少的路径有多少条。

## 输入 ##

01010101001011001001010110010110100100001000101010
    00001000100000101010010000100000001001100110100101
    01111011010010001000001101001011100011000000010000
    01000000001010100011010000101000001010101011001011
    00011111000000101000010010100010100000101100000000
    11001000110101000010101100011010011010101011110111
    00011011010101001001001010000001000101001110000000
    10100000101000100110101010111110011000010000111010
    00111000001010100001100010000001000101001100001001
    11000110100001110010001001010101010101010001101000
    00010000100100000101001010101110100010101010000101
    11100100101001001000010000010101010100100100010100
    00000010000000101011001111010001100000101010100011
    10101010011100001000011000010110011110110100001000
    10101010100001101010100101000010100000111011101001
    10000000101100010000101100101101001011100000000100
    10101001000000010100100001000100000100011110101001
    00101001010101101001010100011010101101110000110101
    11001010000100001100000010100101000001000111000010
    00001000110000110101101000000100101001001000011101
    10100101000101000000001110110010110101101010100001
    00101000010000110101010000100010001001000100010101
    10100001000110010001000010101001010101011111010010
    00000100101000000110010100101001000001000000000010
    11010000001001110111001001000011101001011011101000
    00000110100010001000100000001000011101000000110011
    10101000101000100010001111100010101001010000001000
    10000010100101001010110000000100101010001011101000
    00111100001000010000000110111000000001000000001011
    10000001100111010111010001000110111010101101111000

# 算法分析 #

这道题是标准的bfs题目，可以将所有第一行的起点全部压入队列中进行一次bfs。

但是要多考虑一个问题。

![1][]

**因此存在两种解决方法**

## 方法一： ##

普通的bfs**记录步数**，**新增两个变量mmin,cnt**，只有当第一次到达最后一层时，修改**mmin为当前步数**。

在**当步数等于mmin**，并且**达到最后一层时，cnt++**。

### 如何解决并发性问题呢？ ###

在此方法中不使用true和false去标记vist数组，**用当前到达这个点时，它是第几层到达的点，来进行标记**

**因此vist数组初始化为-1**

## 方法二： ##

在bfs的基础上，在循环时，**不记录步数**，分层次循环，每次将一层处理完之后再去处理下一层。

**即每次将当前步数能够到达的点，全部处理一边，这样就能保证，在不记录步数的情况下，保证后续出现到终点情况时，步数是相同的并且是最小的。**

### 如何解决并发性问题呢？ ###

每次修改时，参照当前层的vist数组，修改下一层的vist1。

**最后在vist数组中无冲突，并且也保证了所有情况修改的综合在vist1中**

## 代码（方法一）（未过，后续修正） ##

#include <bits/stdc++.h> 
    using namespace std;
    
    char s[55][55];
    int vist[55][55];    //记录第几层到达的vist数组
    int fx[4][2] = {
        {
        1,0},{
        -1,0},{
        0,1},{
        0,-1}};
    typedef pair<int, int> pii;
    typedef pair<int ,pii> piii;
    
    int main()
    {
        
        for (int i = 0; i < 30; i++)
            scanf("%s", s[i]);
      
      queue<piii> eq;
      memset(vist, -1, sizeof(vist));
      
      for(int i = 0; i < 50; i++)
        if(s[0][i] == '0'){
        
          pii temp;
          temp.first = 0;
          temp.second = i;
                eq.emplace(0,temp);
          vist[0][i] = 0;
        }
      
      int mmin = 2000, cnt = 0;
      
      while(!eq.empty()){
        
        piii now = eq.front();
        eq.pop();
        
        if(now.first > mmin) break;
        
        for(int i = 0; i < 4; i++){
        
          int nextx = now.second.first + fx[i][0];
          int nexty = now.second.second + fx[i][1];
          
          if(nextx < 0 || nextx >= 30 || nexty < 0 || nexty >= 50) continue;
          if(s[nextx][nexty] == '1') continue;
          
          //当将要访问的点一定要高层访问过或者根本被没访问的点
          if(vist[nextx][nexty] != -1 && vist[nextx][nexty] < now.first + 1) continue;
          if(nextx == 29){
        
            mmin = now.first + 1;
            cnt ++;
          }
          pii temp;
          temp.first = nextx;
          temp.second = nexty;
          eq.emplace(now.first + 1, temp);
          vist[nextx][nexty] = now.first + 1;
        }
      }
      
      cout << cnt << endl;
      
      return 0;
    }

## 代码（方法二） ##

#include <bits/stdc++.h> 
    using namespace std; 
    
    char s[55][55]; 
    bool vist[55][55];	//当前层，用于判断的层
    bool vist1[55][55]; 	//下一层，用于修改的层
    int fx[4][2] = {
        {
        1,0},{
        -1,0},{
        0,1},{
        0,-1}}; 
    
    int main() 
    {
         
      for (int i = 0; i < 30; i++) 
        scanf("%s", s[i]); 
      
      queue<pair<int,int>> eq; 
      for (int i = 0; i < 50; i++) 
        if (s[0][i] == '0') {
         
          eq.emplace(0, i); 
          vist[0][i] = 1; 
        } 
      
      while (1) {
         
        int ans = 0; 
        memcpy(vist1, vist, sizeof(vist)); 	//当前层赋值给下一层
        int cnt = eq.size(); 
        
        if (cnt == 0) 
          return 0; 
        
        //分层bfs
        while (cnt--) {
         
          auto now = eq.front(); 
          eq.pop(); 
          for (int i = 0; i < 4; i++) {
         
            auto nextt = now; 
            nextt.first += fx[i][0]; 
            nextt.second += fx[i][1]; 
            
            if (nextt.first < 0 || nextt.first >= 30 || nextt.second < 0 || nextt.second >= 50) continue; 
            if (s[nextt.first][nextt.second] == '1') continue; 
            if (nextt.first == 29) ans++; 	//到达出口
            if (vist[nextt.first][nextt.second]) continue; 	//查看当前这层vist数组
            //改变下一层的vist数组
            //一层修改一次vist数组，最后综合在vist1数组中
            vist1[nextt.first][nextt.second] = 1; 	
            eq.emplace(nextt); 
          } 
        }
        //分层bfs
        
        //如果在这层就到达了出口就说明是最短的，并且所有的都记录在内了
        if (ans) 
          return printf("%d\n", ans), 0; 
        //如果在这层就到达了出口就说明是最短的，并且所有的都记录在内了
        
        memcpy(vist, vist1, sizeof(vist)); 	//将下一层赋值给当前层
      }
      return 0; 
    }

[1]: /images/20221120/914c8603fb544295ac975c5034d590b4.png