首页 > 代码库 > [LeetCode]Surrounded Regions

[LeetCode]Surrounded Regions

题目:Surrounded Regions

给定一个二维矩阵由‘x‘和‘o‘表示,其中o被x包围了,如果o上下左右中有其他的o,则被看做是连在一起的,而一起的o中有一个贴边了,就表示这些o都是活的。死的o要替换成x。

思路:

采用广度优先搜索或深度优先搜索来找到连在一起的o;只要遍历过程中有一个贴边的就不在继续搜索,并将现在搜索到的所有活节点全部换成A;

我实际上采用的是广度优先搜索;在搜索过程中未确定的节点我将其转换成了B,最后能判断他的死活时,再转换成对应的标记。

起始外循环是按照从上到下、从左到右的顺序搜索的下面的checkEnclosed函数并不需要再去看它上面的节点或其同一行的右边的点,这些点是判断过得,只有A和X两种可能。

void LeetCode::checkEnclosed(vector<vector<char>>& board, const pair<int, int> cur){
    bool flag = false;//标记当前检查的一系列节点是否为活节点
    queue<pair<int, int>>Q;
    vector<pair<int, int>> nodes;//候选节点列表
    Q.push(cur);
    while (!Q.empty()){
        pair<int, int> p = Q.front();
        //存在上面的节点,此处在solve应用中不需要,因为是从上到下,从左到右,如果存在上面和左面的节点必然是活节点
        if (p.first < cur.first || (p.first == cur.first && p.second < cur.second)){
            flag = true;
            break;
        }
        if (!p.first || p.first == board.size() - 1 || !p.second || p.second == board.at(0).size() - 1){//在边界上,是活节点
            flag = true;
            break;//以确定死活,不再继续搜索
        }
        //死活暂时未知,要看邻接节点的死活
        if (board.at(p.first - 1).at(p.second) == A){
            flag = true;
            break;
        }
        else if (board.at(p.first - 1).at(p.second) == O){//存在上边的节点
            board.at(p.first - 1).at(p.second) = B;
            pair<int, int>temp(p.first - 1, p.second);
            Q.push(temp);
        }

        if (board.at(p.first).at(p.second + 1) == A){
            flag = true;
            break;
        }
        else if (board.at(p.first).at(p.second + 1) == O){//存在右边的节点
            board.at(p.first).at(p.second + 1) = B;
            pair<int, int>temp(p.first, p.second + 1);
            Q.push(temp);
        }
        if (board.at(p.first + 1).at(p.second) == A){
            flag = true;
            break;
        }
        else if (board.at(p.first + 1).at(p.second) == O){//存在下边的节点
            board.at(p.first + 1).at(p.second) = B;
            pair<int, int>temp(p.first + 1, p.second);
            Q.push(temp);
        }
        if (board.at(p.first).at(p.second - 1) == A){
            flag = true;
            break;
        }
        else if (board.at(p.first).at(p.second - 1) == O){//存在左边的节点
            board.at(p.first).at(p.second - 1) = B;
            pair<int, int>temp(p.first, p.second - 1);
            Q.push(temp);
        }
        Q.pop();
        nodes.push_back(p);//放入候选列表中
    }
    while (!Q.empty()){//将队列中剩余的节点放到候选列表中
        pair<int, int> p = Q.front();
        Q.pop();
        nodes.push_back(p);
    }
    if (!flag){//候选列表中的是死节点
        auto it = nodes.begin();
        while (it != nodes.end()){
            board.at((*it).first).at((*it).second) = X;//改为死节点
            ++it;
        }
    }
    else{
        auto it = nodes.begin();
        while (it != nodes.end()){
            board.at((*it).first).at((*it).second) = A;//标记活节点
            ++it;
        }
    }
}

void LeetCode::solve(vector<vector<char>>& board){
    stack<pair<int, int>>s;
    for (vector<int>::size_type i = 0; i < board.size(); i++){
        for (vector<int>::size_type j = 0; j < board.at(i).size(); j++){
            if (board.at(i).at(j) == O){//需要判断死活的子
                pair<int, int>temp(i, j);
                checkEnclosed(board, temp);
            }
        }
    }
    for (vector<int>::size_type i = 0; i < board.size(); i++){
        for (vector<int>::size_type j = 0; j < board.at(i).size(); j++){
            if (board.at(i).at(j) == A){//用于标记的活节点
                board.at(i).at(j) = O;
            }
        }
    }
}

题目:Number of Islands

给定一个二维矩阵由‘1‘和‘0‘表示,其中0表示水,1表示岛屿,上下左右相同表示联通,多个1连成一座岛屿;找岛屿的个数。

思路:

和上面类似,广度优先搜索找到所有与当前节点是一个岛屿的点,并将它们都设为2。

int LeetCode::numIslands(vector<vector<char>>& grid){
    int count = 0;
    queue<pair<int, int>>Q;//记录广度优先搜索的节点
    for (size_t i = 0; i < grid.size(); ++i){
        for (size_t j = 0; j < grid.at(0).size(); ++j){
            if (grid.at(i).at(j) == 1){//需要判断是否是岛
                ++count;
                Q.push(make_pair(i,j));
                grid.at(i).at(j) = 2;
                while (!Q.empty()){
                    auto p = Q.front();
                    Q.pop();
                    if (p.first > 0 && grid.at(p.first - 1).at(p.second) == 1){
                        Q.push(make_pair(p.first - 1, p.second));//左边
                        grid.at(p.first - 1).at(p.second) = 2;//立即设为2,防止重复添加
                    }
                    if (p.second > 0 && grid.at(p.first).at(p.second - 1) == 1){
                        Q.push(make_pair(p.first, p.second - 1));//上边
                        grid.at(p.first).at(p.second - 1) = 2;
                    }
                    if (p.first < grid.size() - 1 && grid.at(p.first + 1).at(p.second) == 1){
                        Q.push(make_pair(p.first + 1, p.second));//右边
                        grid.at(p.first + 1).at(p.second) = 2;
                    }
                    if (p.second < grid.at(0).size() - 1 && grid.at(p.first).at(p.second + 1) == 1){
                        Q.push(make_pair(p.first, p.second + 1));//下边
                        grid.at(p.first).at(p.second + 1) = 2;
                    }
                }
            }
        }
    }

    for (size_t i = 0; i < grid.size(); ++i){
        for (size_t j = 0; j < grid.at(0).size(); ++j){
            if (grid.at(i).at(j) == 2){//将2还原为1
                grid.at(i).at(j) = 1;
            }
        }
    }
    return count;
}

下面是深度优先搜索的实现

int LeetCode::numIslands(vector<vector<char>>& grid){
    int count = 0;
    stack<pair<int, int>>s;//记录深度优先搜索的节点
    for (size_t i = 0; i < grid.size(); ++i){
        for (size_t j = 0; j < grid.at(0).size(); ++j){
            if (grid.at(i).at(j) == 1){//需要判断是否是岛
                ++count;
                s.push(make_pair(i, j));
                grid.at(i).at(j) = 2;
                while (!s.empty()){
                    auto p = s.top();
                    if (p.first > 0 && grid.at(p.first - 1).at(p.second) == 1){
                        s.push(make_pair(p.first - 1, p.second));//左边
                        grid.at(p.first - 1).at(p.second) = 2;//立即设为2,防止重复添加
                    }else if (p.second > 0 && grid.at(p.first).at(p.second - 1) == 1){
                        s.push(make_pair(p.first, p.second - 1));//上边
                        grid.at(p.first).at(p.second - 1) = 2;
                    }else if (p.first < grid.size() - 1 && grid.at(p.first + 1).at(p.second) == 1){
                        s.push(make_pair(p.first + 1, p.second));//右边
                        grid.at(p.first + 1).at(p.second) = 2;
                    }else if (p.second < grid.at(0).size() - 1 && grid.at(p.first).at(p.second + 1) == 1){
                        s.push(make_pair(p.first, p.second + 1));//下边
                        grid.at(p.first).at(p.second + 1) = 2;
                    }
                    else{//回溯
                        s.pop();
                    }
                }
            }
        }
    }

    for (size_t i = 0; i < grid.size(); ++i){
        for (size_t j = 0; j < grid.at(0).size(); ++j){
            if (grid.at(i).at(j) == 2){//将2还原为1
                grid.at(i).at(j) = 1;
            }
        }
    }
    return count;
}

 

[LeetCode]Surrounded Regions