We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. DFS: Connected Cell in a Grid
  2. Discussions

DFS: Connected Cell in a Grid

Sort by

recency

|

231 Discussions

|

  • dehaka
     + 0 comments

    why do they want DFS? component size problems are more intuitively done with BFS.

    DFS recursive, not iterative:

    vector<int> S = {-1, 0, 1};

void component(int i, int j, int n, int m, const vector<vector<int>>& grid, vector<vector<bool>>& visited, int& size) {
    visited[i][j] = true;
    ++size;
    for (int I : S) {
        for (int J : S) {
            if (i+I < 0 or i+I >= n or j+J < 0 or j+J >= m or visited[i+I][j+J] or grid[i+I][j+J] == 0) continue;
            component(i+I, j+J, n, m, grid, visited, size);
        }
    }
}

int maxRegion(int n, int m, const vector<vector<int>>& grid) {
    vector<int> components;
    vector<vector<bool>> visited(n, vector<bool>(m));
    int size = 0;
    for (int i=0; i < n; ++i) {
        for (int j=0; j < m; ++j) {
            if (visited[i][j] or grid[i][j] == 0) continue;
            size = 0;
            component(i, j, n, m, grid, visited, size);
            components.push_back(size);
        }
    }
    return *max_element(components.begin(), components.end());
}

int main()
{
    int n, m, k;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m));
    for (int i=0; i < n; ++i) {
        for (int j=0; j < m; ++j) {
            cin >> k;
            grid[i][j] = k;
        }
    }
    cout << maxRegion(n, m, grid);
}

  • morgehowie
     + 1 comment

    This was my timed solution. I am not very good a t matrix problems so if anyone could view my code and tell me why it may be abd or ugly or any improvements I'd greatly appreciate it!

    int maxRegion(vector> grid) { int max_region_amt = 0; int n = grid.size(); int m = grid[0].size(); stack q; vector visited(n*m); int i = 0; while(i < n * m){

        if(grid[i / m][i % m]){
        break;
    }
     visited[i] = true;
    ++i;
}

while (i < n*m && !visited[i]) {
    visited[i] = true;
    int amt_region = 1;
    q.push(i);
    cout << "New iteration: " << i << "\n";
    while(q.size()){
        int curr_value = q.top();
        q.pop();
        if(curr_value / m != 0){
            int prev_row =(curr_value - m)/m;
            if(!visited[curr_value - m]){
                visited[curr_value - m] = true;
                if(grid[prev_row][curr_value % m]){
                        q.push(curr_value - m);
                        amt_region++;
                    }
            }
            if(curr_value % m && !visited[curr_value - m - 1]){
                visited[curr_value - m - 1] = true;;
                if(grid[prev_row][curr_value % m -1]){
                    q.push(curr_value - m - 1);
                    amt_region++;
                }
            }
            if((curr_value + 1) % m && !visited[curr_value - m + 1]){
                visited[curr_value - m + 1] = true;;
                if(grid[prev_row][curr_value % m +1]){
                    q.push(curr_value - m + 1);
                    amt_region++;
                }
            }
        }
        if(curr_value / m + 1 != n){
            int next_row =(curr_value + m)/m;
            if(!visited[curr_value + m]){
                visited[curr_value + m] = true;
                if(grid[next_row][curr_value % m]){
                        q.push(curr_value + m);
                        amt_region++;
                    }
            }
            if(curr_value % m && !visited[curr_value + m - 1]){
                visited[curr_value + m - 1] = true;;
                if(grid[next_row][curr_value % m - 1]){
                    q.push(curr_value + m - 1);
                    amt_region++;
                }
            }
            if((curr_value + 1) % m && !visited[curr_value + m + 1]){
                visited[curr_value + m + 1] = true;;
                if(grid[next_row][curr_value % m +1]){
                    q.push(curr_value + m + 1);
                    amt_region++;
                }
            }
        }
        if((curr_value + 1) % m && !visited[curr_value + 1]){
            visited[curr_value + 1] = true;;
            if(grid[curr_value / m][curr_value % m +1]){
                q.push(curr_value + 1);
                amt_region++;
            }
        }
        if((curr_value) % m && !visited[curr_value - 1]){
            visited[curr_value - 1] = true;
            if(grid[curr_value / m][curr_value % m - 1]){
                q.push(curr_value +-1);
                amt_region++;
            }
        }

        while(i < n * m && (visited[i] || !grid[i / m][i % m])){
            visited[i] = true;
            ++i;
        }
    }
    max_region_amt = max(max_region_amt, amt_region);
}




cout << i << "\n";
return max_region_amt;

    }

    • dehaka
       + 0 comments

      look at my post. this is a very simply question, though more intuitive with BFS instead of DFS

  • dmadisetti
     + 0 comments

    All the graph methods are reasonable and make sense given the category

    However, is it possible to solve this with a couple convolutional passes?

  • bordax
     + 0 comments

    Python

    def neighborhood(i, j):
    return [(i+1, j), (i-1, j), (i, j+1), (i, j-1), (i+1, j+1), (i-1, j-1), (i-1, j+1), (i+1, j-1)]

def maxRegion(grid):
    largest_region_size = 0
    visited = set()
    for i in range(len(grid)-1):
        for j in range(len(grid[0])):
            if (i, j) in visited or grid[i][j] == 0:
                continue
            region_size = 1
            visited.add((i, j))
            stack = neighborhood(i, j)
            while stack:
                curr = stack.pop()
                if curr in visited or curr[0] < 0 or curr[1] < 0:
                    continue
                try:
                    if grid[curr[0]][curr[1]] == 0:
                        continue
                except:
                    continue
                visited.add((curr[0], curr[1]))
                region_size += 1
                stack.extend(neighborhood(curr[0], curr[1]))
            largest_region_size = max(largest_region_size, region_size)
                
            
    return largest_region_size

  • sakshikishore191
     + 0 comments

    Simple Java Solution

    public static int maxRegion(List<List<Integer>> grid) {
    // Write your code here
    int max=0;
    int visited[][]=new int[grid.size()][grid.get(0).size()];
    for(int i=0;i<grid.size();i++)
    {
        for(int j=0;j<grid.get(0).size();j++)
        {
            if(grid.get(i).get(j)==1 && visited[i][j]==0)
            {
                visited[i][j]=1;
                int count=0;
                Queue<String> q=new LinkedList<String>();
                q.add(Integer.toString(i)+" "+Integer.toString(j));
                while(q.size()>0)
                {
                    String str[]=q.poll().split(" ");
                    count++;
                    int x=Integer.parseInt(str[0]);
                    int y=Integer.parseInt(str[1]);
                    if(x-1>=0 && grid.get(x-1).get(y)==1 && visited[x-1][y]==0)
                    {
                        visited[x-1][y]=1;
                        q.add(Integer.toString(x-1)+" "+Integer.toString(y));
                    }
                    if(y-1>=0 && grid.get(x).get(y-1)==1 && visited[x][y-1]==0)
                    {
                        visited[x][y-1]=1;
                        q.add(Integer.toString(x)+" "+Integer.toString(y-1));
                    }
                    if(x+1<grid.size() && grid.get(x+1).get(y)==1 && visited[x+1][y]==0)
                    {
                        visited[x+1][y]=1;
                        q.add(Integer.toString(x+1)+" "+Integer.toString(y));
                    }
                    if(y+1<grid.get(0).size() && grid.get(x).get(y+1)==1 && visited[x][y+1]==0)
                    {
                        visited[x][y+1]=1;
                        q.add(Integer.toString(x)+" "+Integer.toString(y+1));
                    }
                    if(x-1>=0 && y-1>=0 && grid.get(x-1).get(y-1)==1 && visited[x-1][y-1]==0)
                    {
                        visited[x-1][y-1]=1;
                        q.add(Integer.toString(x-1)+" "+Integer.toString(y-1));
                    }
                    if(x-1>=0 && y+1<grid.get(0).size() && grid.get(x-1).get(y+1)==1 && visited[x-1][y+1]==0)
                    {
                        visited[x-1][y+1]=1;
                        q.add(Integer.toString(x-1)+" "+Integer.toString(y+1));
                    }
                    if(x+1<grid.size() && y+1<grid.get(0).size() && grid.get(x+1).get(y+1)==1 && visited[x+1][y+1]==0)
                    {
                        visited[x+1][y+1]=1;
                        q.add(Integer.toString(x+1)+" "+Integer.toString(y+1));
                    }
                    if(x+1<grid.size() && y-1>=0 && grid.get(x+1).get(y-1)==1 && visited[x+1][y-1]==0)
                    {
                        visited[x+1][y-1]=1;
                        q.add(Integer.toString(x+1)+" "+Integer.toString(y-1));
                    }
                    
                }
                if(count>max)
                {
                    max=count;
                }
            }
        }
    }
    
    return max;

    }

Join us

Create a HackerRank account

Be part of a 26 million-strong community of developers

Already have an account?Log in