DFS: Connected Cell in a Grid

  • + 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;
    

    }