C++迷宫问题：为什么测试用例未完全通过？

Question

如图所示，测试用例过了大部分，代码哪里有问题呢？

class Solution {
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int m=maze.size(),n=maze[0].size();
        //标记数组
        int vis[m][n];
        memset(vis,0,sizeof(vis));
        //创建队列用于BFS
        queue<pair<int ,int>> q;
        q.push({entrance[0],entrance[1]});
        vis[entrance[0]][entrance[1]]=true;
        //开始BFS遍历
        int step=0;
        while(q.size())
        {
            step++;
            for(int i=0;i<q.size();i++)
            {
                auto [a,b]=q.front();
                q.pop();
                for(int j=0;j<4;j++)
                {
                    int x=a+dx[j];
                    int y=b+dy[j];
                    if(x>=0&&x<m&&y>=0&&y<n&&!vis[x][y]&&maze[x][y]=='.')
                    {
                        //判断是否为出口
                        if(x==0||x==m-1||y==0||y==n-1) return step;
                        q.push({x,y});
                        vis[x][y]=true;
                    }
                }
            }
        }
        return -1;
    }
};

Answer 1

class Solution {
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int m = maze.size(), n = maze[0].size();
        vector<vector<bool>> vis(m, vector<bool>(n, false));
        queue<pair<int, int>> q;
        q.push({entrance[0], entrance[1]});
        vis[entrance[0]][entrance[1]] = true;
        // 开始 BFS 遍历
        int step = 0;
        while(!q.empty()) {
            int size = q.size(); 
            step++;
            for(int i = 0; i < size; i++) {
                auto [a, b] = q.front();
                q.pop();
                for(int j = 0; j < 4; j++) {
                    int x = a + dx[j];
                    int y = b + dy[j];
                    if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && maze[x][y] == '.') {
                        
                        if(x == 0 || x == m-1 || y == 0 || y == n-1) return step;
                        q.push({x, y});
                        vis[x][y] = true;
                    }
                }
            }
        }
        return -1;
    }
};

Answer 2

class Solution {
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int m = maze.size(), n = maze[0].size();
        // 标记数组
        vector<vector<int>> vis(m, vector<int>(n, 0));
        // 创建队列用于BFS
        queue<pair<int, int>> q;
        q.push({entrance[0], entrance[1]});
        vis[entrance[0]][entrance[1]] = true;
        // 开始BFS遍历
        int step = 0;
        while (!q.empty()) {
            int size = q.size();
            step++;
            for (int i = 0; i < size; i++) {
                auto [a, b] = q.front();
                q.pop();
                for (int j = 0; j < 4; j++) {
                    int x = a + dx[j];
                    int y = b + dy[j];
                    if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && maze[x][y] == '.') {
                        // 判断是否为出口
                        if (x == 0 || x == m - 1 || y == 0 || y == n - 1) return step;
                        q.push({x, y});
                        vis[x][y] = true;
                    }
                }
            }
        }
        return -1;
    }
};

修改内容：

1.队列大小计算：在循环之前将队列的初始大小存储在变量 size 中，以确保正确的迭代次数。
2.vis 数组的初始化：使用 vector<vector<int>> 来初始化 vis 数组，以确保正确初始化。

直接在循环中使用 q.size() 和提前将 q.size() 存储在变量中有一些关键区别：

1.动态变化：如果直接在循环中使用 q.size()，每次迭代时都会重新计算队列的大小。如果在循环体内对队列进行了修改（例如 q.push() 或 q.pop()），这会导致 q.size() 的值发生变化，从而影响循环的执行次数。
2.性能：每次调用 q.size() 都会计算队列的大小，虽然这个操作通常是常数时间复杂度，但在某些情况下，频繁调用可能会稍微影响性能。提前将 q.size() 存储在变量中可以避免重复计算。
3.逻辑正确性：在 BFS 中，通常希望在处理当前层的所有节点后再进入下一层。如果直接使用 q.size()，队列大小的动态变化可能会导致在处理当前层时意外地处理了下一层的节点。提前存储队列大小可以确保只处理当前层的节点。