# QM20A - Editorial

Author: Chandan Boruah
Tester: Harsh Raj
Editorialist: Chandan Boruah

EASY

# PREREQUISITES:

Graph Theory, Flood Fill.

# PROBLEM:

Given a 2D grid, print if all empty cells can be reached when a flood fill algorithm is run on one of the empty cells.

# QUICK EXPLANATION:

Select any empty cell and run the flood fill algorithm, and check if all cells have been reached.

# EXPLANATION:

Select any empty cell and run a graph traversal algorithm, such that all the neighboring cells that can be reached are traversed. If all the cells are traversed, then print 1 else print 0.

# SOLUTIONS:

chandubaba's Solution
``````using System;
using System.Collections.Generic;
class some
{
public static void Main()
{
int x=int.Parse(ss[0]);
int y=int.Parse(ss[1]);
int[,]arr=new int[x,y];
int indx=-1;
int indy=-1;
for(int i=0;i<x;i++)
{
for(int j=0;j<y;j++)
{
arr[i,j]=((s[j]=='.')?0:1);
if(indx==-1)
{
if(arr[i,j]==0){indx=i;indy=j;}
}
}
}
Queue<int>qq=new Queue<int>();
List<string>done=new List<string>();
qq.Enqueue(indx);
qq.Enqueue(indy);
arr[indx,indy]=1;
int[]dx={0,0,1,-1};
int[]dy={-1,1,0,0};
while(qq.Count>0)
{
int qx=qq.Dequeue();
int qy=qq.Dequeue();
for(int i=0;i<dx.Length;i++)
{
int xx=dx[i]+qx;
int yy=dy[i]+qy;
if(xx>=0 && yy>=0 && xx<x && yy<y)
{
if(arr[xx,yy]==1)continue;
if(!done.Contains(xx+" "+yy))
{
qq.Enqueue(xx);
qq.Enqueue(yy);
arr[xx,yy]=1;
}
}
}
}
bool isOne=true;
for(int i=0;i<x;i++)
{
for(int j=0;j<y;j++)
{
if(arr[i,j]==0)isOne=false;
}
}
if(isOne)Console.WriteLine(1);
else Console.WriteLine(0);
}
}
``````
harshraj22's Solution
``````#include<bits/stdc++.h>
using namespace std;

#define ll long long int
const int N = 52;
char arr[N][N];
bool visited[N][N];
int x,y;

void dfs(int i,int j){
if(i <= 0 || j <=0)
return;
else if(i > x || j > y)
return;
else if(visited[i][j])
return ;
else if(arr[i][j] == '#')
return;
visited[i][j] = true;
dfs(i-1,j); dfs(i+1,j); dfs(i,j-1); dfs(i,j+1);
}

int main(){
for(int i=0;i<N;i++){
for(int j=0;j<N;j++)
visited[i][j] = false;
}
cin >> x >> y;
for(int i=1;i<=x;i++){
for(int j=1;j<=y;j++){
cin >> arr[i][j];
}
}

bool donut = false;
dfs(1,1);
dfs(1,y);
dfs(x,1);
dfs(x,y);

for(int i=1;i<=x;i++){
for(int j=1;j<=y;j++){
if(arr[i][j] == '.' && visited[i][j] == false)
donut = true;
}
}

if(donut)
cout << "0\n";
else
cout << "1\n";

return 0;
}
``````