CDEC2205 -Editorial

PROBLEM LINK: Contest Page | CodeChef

Author: arish8_2
Tester: aman_gupta2486
Editorialist: arish8_2

DIFFICULTY:

EASY, MEDIUM

PREREQUISITES:

Graph, dfs, dfs on grid

PROBLEM:

Chef had won a big lottery in Chefland’s biggest fair. He decided to buy a single-floor apartment. The apartment has rooms and corridors connecting them.

The Apartment is represented in the 2D grid, where parts of rooms are represented by 1’s and corridors by 0’s. Here all the 1’s surrounded by 0’s or ends of the grid are considered as a single room.

Example:

1 0 1 1

1 0 0 0

0 0 1 1

[(0,0),(1,0)][(0,0),(1,0)] is first room, [(0,2),(0,3)][(0,2),(0,3)] is second room and [(2,2),(2,3)][(2,2),(2,3)] is third room, so here apartment had a total of 3 rooms.

Chef wanted to know how many rooms he had in total, so he asked you for help. Help him figure out how many rooms there are in the apartment.

QUICK EXPLANATION:

Apply dfs on grid.

EXPLANATION:

Run dfs for each cell of the grid whose values are 1 and count it as one room. While dfs runs for each cell mark the cells as visited.
For Example:

1 0 1 1
1 0 0 1

For the above example, run dfs for each cell that is marked 1, and count it as one room. Dfs function will mark all the connected cells as visited (here, (0,0) and (1,0) are connected. Hence both the cells will be marked as visited). Now it will repeat the same process for cell (0,2) and will mark (0,2), (0,3) and (1,3) as visited and count it as 2nd room. Now, dfs will not run for other cells.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;

int n,m;
vector<vector<int>> vis(1000,vector<int> (1000,0));

bool isvalid(int x,int y){
    if(x<0 || x>n-1 || y<0 || y>m-1) return false; // returns false if x or y moving outside the grid
    if(vis[x][y]==0 || vis[x][y]==2) return false; // returns false if cell is marked 0 (as corridor) or 2 ( as visited )
    return true;
}
void dfs(int x,int y){

    vis[x][y]=2;

    if(isvalid(x-1,y)) // up direction
        dfs(x-1,y);
    if(isvalid(x+1,y)) // down direction
        dfs(x+1,y);
    if(isvalid(x,y-1)) // left direction
        dfs(x,y-1);
    if(isvalid(x,y+1)) // right direction
        dfs(x,y+1);
}

int main(){
    int T;
    cin>>T;
    while(T--){
        cin>>n>>m;
        vector<vector<int>> arr(n,vector<int> (m));
        for(int i=0; i < n ; i++)
            for(int j=0; j < m ; j++)
                cin>>vis[i][j];
        int c=0;
        for(int i=0; i < n ; i++){
            for(int j=0; j < m ; j++){
                if(vis[i][j]==1){
                    c++; // counts the rooms
                    dfs(i,j); // running dfs for each cell
                }
            }
        }
        cout<<c<<"\n";
    }
    return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> g(1005,vector<int>(1005));

void dfs(int i,int j,int n,int m)
{
    if(i<0 || i>=n || j<0 || j>=m || g[i][j]!=1)
    {
        return;
    }
    
    g[i][j]=2;
    
    dfs(i+1,j,n,m);
    dfs(i,j+1,n,m);
    dfs(i-1,j,n,m);
    dfs(i,j-1,n,m);
    
}

int main() {
    int t;
    cin>>t;
    while (t--) {

        int n, m;
        cin>>n>>m;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin>>g[i][j];
            }
        }

        int ans=0;
    
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(g[i][j]==1)
            {
                dfs(i,j,n,m);
                ans++;
            }
        }
    }
        cout<<ans<<endl;
    }
    return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

int n,m;
vector<vector<int>> vis(1000,vector<int> (1000,0));

bool isvalid(int x,int y){
    if(x<0 || x>n-1 || y<0 || y>m-1) return false; // returns false if x or y moving outside the grid
    if(vis[x][y]==0 || vis[x][y]==2) return false; // returns false if cell is marked 0 (as corridor) or 2 ( as visited )
    return true;
}
void dfs(int x,int y){

    vis[x][y]=2;

    if(isvalid(x-1,y)) // up direction
        dfs(x-1,y);
    if(isvalid(x+1,y)) // down direction
        dfs(x+1,y);
    if(isvalid(x,y-1)) // left direction
        dfs(x,y-1);
    if(isvalid(x,y+1)) // right direction
        dfs(x,y+1);
}

int main(){
    int T;
    cin>>T;
    while(T--){
        cin>>n>>m;
        vector<vector<int>> arr(n,vector<int> (m));
        for(int i=0; i < n ; i++)
            for(int j=0; j < m ; j++)
                cin>>vis[i][j];
        int c=0;
        for(int i=0; i < n ; i++){
            for(int j=0; j < m ; j++){
                if(vis[i][j]==1){
                    c++; // counts the rooms
                    dfs(i,j); // running dfs for each cell
                }
            }
        }
        cout<<c<<"\n";
    }
    return 0;
}