PROBLEM LINK:
Author: Chandan Boruah
Tester: Harsh Raj
Editorialist: Chandan Boruah
DIFFICULTY:
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()
{
string[]ss=Console.ReadLine().Split();
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++)
{
string s=Console.ReadLine();
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);
done.Add(indx+" "+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))
{
done.Add(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;
}