L1926. bfs

二维数组初始化

   int d[m][n];
   memset(d,-1,sizeof d);
1
2

令d数组初始为-1，再把入口变0，这样-1即代表没有访问过，非-1即代表距离，一个数组记录两种数值。

class Solution {
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int m=maze.size();
        int n=maze[0].size();
        int dx[4]={1,0,-1,0};
        int dy[4]={0,1,0,-1};
        int d[m][n];
        memset(d,-1,sizeof d);
        queue<pair<int,int>> q;
        d[entrance[0]][entrance[1]]=0;
        q.push({entrance[0],entrance[1]});
        while(!q.empty()){
            auto tmp= q.front();
            q.pop();
            for(int i=0;i<4;i++){
                int x=tmp.first+dx[i];
                int y=tmp.second+dy[i];
                if(x>=0 && x<m && y>=0 &&y<n &&maze[x][y]=='.' && d[x][y]==-1){
                    d[x][y]=d[tmp.first][tmp.second]+1;
                    q.push({x,y});
                    if(x==0 ||y==0 || x==m-1 ||y==n-1) return d[x][y];
                }
            }
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28