Help with bfs


  • 0
    B

    can anyone help me? my bfs has a time limit exceed problem for some test cases...
    class Solution {
    public:
    int numIslands(vector<vector<char>>& grid) {
    if(grid.size() == 0) return 0;
    int row = grid.size();
    int column = grid[0].size();
    int size = row * column;
    vector<string> vec;
    for(int i = 0; i < size; i++)
    {
    vec.push_back("unvisited");
    }
    int result = 0;
    for(int i = 0; i < size; i++){
    int tx = i % column;
    int ty = i / column;
    if(vec[i] == "unvisited" && grid[ty][tx] == '1')
    {
    result++;
    queue<int>q;
    q.push(i);
    vec[i] = "visited";
    while(!q.empty())
    {
    int head = q.front();
    vec[head] = "visited";
    int x = head % column;
    int y = head / column;
    q.pop();
    if(x + 1 < column && grid[y][x + 1] == '1' && vec[head + 1] == "unvisited")
    q.push(head + 1);
    if(y + 1 < row && grid[y + 1][x] == '1' && vec[head + column] == "unvisited")
    q.push(head + column);
    if(x - 1 >= 0 && grid[y][x - 1] == '1' && vec[head - 1] == "unvisited")
    q.push(head - 1);
    if(y - 1 >= 0 && grid[y - 1][x] == '1' && vec[head - column] == "unvisited")
    q.push(head - column);
    }
    }
    }
    return result;
    }
    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.