PROBLEM LINK: CodeChef: Practical coding for everyone
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;
}