QM20A - Editorial

PROBLEM LINK:

Practice
Contest

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;
}