题目描述

blablabla

样例

blablabla

算法1

// Solution 1 : distance 数组记录距离

#include <iostream>
#include <queue>
using namespace std;

int bfs(vector<vector<int>> matrix){
    queue<pair<int,int>> q;
    vector<vector<int>> dist(matrix.size(), vector<int>(matrix[0].size(), 0));
    q.push({0,0});
    int n = matrix.size(), m = matrix[0].size();
    int dx[]={0, 0, -1, 1}, dy[] = {1, -1, 0, 0};
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int a = x+dx[i], b =  y+dy[i];
            if(a >= 0 && a < n && b >= 0 && b < m && matrix[a][b] != -1 && matrix[a][b] != 1){
                q.push({a, b});
                dist[a][b] = dist[x][y]+1;
                matrix[a][b] = -1;
            }
        }
    }
    return dist[n-1][m-1];
}

int main(void){
    int n, m;
    cin >> n >> m;
    vector<vector<int>> matrix(n, vector<int>(m, 0));
    for(int i = 0; i < n; i++)
        for(int j =0; j <m; j++)
            cin >> matrix[i][j];
    cout << bfs(matrix) << endl;
    return 0; 
}

算法2

// Solution 2 : 第二种写法， 不需要distance 数组，单变量记录。

#include <iostream>
#include <queue>
using namespace std;

int bfs(vector<vector<int>> matrix){
    int distance = 0;
    int n = matrix.size(), m = matrix[0].size();
    int dx[] = {0,0,-1,1}, dy[] = {1,-1,0,0};
    queue<pair<int,int>> q;
    q.push({0,0});
    while(!q.empty()){
        int q_size = q.size();
        for(int i = 0; i < q_size; i++){
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            if(x == n-1 && y == m-1)    return distance;
            for(int j = 0; j < 4; j++){
                int a = x + dx[j];
                int b = y + dy[j];
                if(a >= 0 && a < n && b >= 0 && b < m && matrix[a][b] != -1 && matrix[a][b] != 1){
                    q.push({a,b});
                    matrix[a][b] = -1;
                }
            }
        }
        distance++;
    }
    return distance;
}

int main(void){
    int n, m;
    cin >> n >> m;
    vector<vector<int>> matrix(n, vector<int>(m, 0));
    for(int i = 0; i < n; i++)
        for(int j =0; j <m; j++)
            cin >> matrix[i][j];
    cout << bfs(matrix) << endl;
    return 0; 
}