C++类中如何获取vector尺寸并定义可全局访问的visited数组

错误原因分析 #

• 类成员变量的默认初始化是在类实例构造的时候执行的，此时grid参数还没有传入numIslands函数，根本不存在，所以不可能用grid.size()给成员变量m、n赋初值
• C++的栈上静态数组int visited[m][n]要求m、n必须是编译期就能确定的常量，动态尺寸的数组不能用这种声明方式，必须用vector这类动态容器
• 原代码还有逻辑错误：内层循环变量误写为i、岛屿计数count的累加位置错误，会导致计数结果不对

正确修改后的代码 #

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

class Solution {
public:
    // 方向数组是编译期常量，保留为静态成员即可
    static constexpr int dx[] = {0, 1, -1, 0};
    static constexpr int dy[] = {1, 0, 0, -1};
    // visited作为类成员vector，各个成员函数都可以访问
    vector<vector<bool>> visited;

    bool is_visited(int x, int y, vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        if (x >= 0 && x < m && y >= 0 && y < n) {
            return !visited[x][y] && grid[x][y] == '1';
        }
        return false;
    }

    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty()) return 0;
        int m = grid.size();
        int n = grid[0].size();
        // 初始化visited数组，尺寸和grid一致，初始值全为false
        visited.assign(m, vector<bool>(n, false));
        int count = 0;

        for (int i = 0; i < m; ++i) {
            // 原代码误写为i < grid[i].size()，修正为j遍历
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    // 每找到一个未访问的陆地块，岛屿数+1
                    count++;
                    queue<pair<int, int>> q;
                    q.push({i, j});
                    visited[i][j] = true;

                    while (!q.empty()) {
                        auto curr = q.front();
                        q.pop();
                        int x = curr.first;
                        int y = curr.second;

                        for (int k = 0; k < 4; ++k) {
                            int newX = x + dx[k];
                            int newY = y + dy[k];
                            if (is_visited(newX, newY, grid)) {
                                visited[newX][newY] = true;
                                q.push({newX, newY});
                            }
                        }
                    }
                }
            }
        }
        return count;
    }
};
// 静态成员变量的类外定义，部分编译器要求必须加
constexpr int Solution::dx[];
constexpr int Solution::dy[];

核心修改说明 #

• 用vector<vector<bool>> visited作为类成员变量，替代原来的静态数组，动态尺寸可以在运行时确定，所有成员函数都可以直接访问
• m、n不需要作为类成员，直接在用到的地方从grid获取即可，或者也可以在numIslands里计算后作为参数传给辅助函数，避免重复计算
• 修正了原代码的逻辑错误：内层循环变量改为j、岛屿计数count放到找到新连通分量的分支里累加，避免多计数
• visited数组在numIslands入口处调用assign方法初始化尺寸和初始值，完全适配输入grid的动态尺寸

内容的提问来源于stack exchange，提问作者Alexander