PROBLEM LINK:
Setter/Tester/Editorialist: Chandan Boruah
DIFFICULTY:
Medium
PREREQUISITES:
Graph Theory
PROBLEM:
Given a grid with obstacles, an initial position and a few positions to reach, find if you can reach all the positions to reach from the initial position.
QUICK EXPLANATION:
Traverse the graph from the initial position, everytime you reach a destination position increment counter.
EXPLANATION:
Count the number of destination positions. Do a graph traversal from the initial position. If you find a destination position, then increment counter. If the counter is equal to the count of the number of destinations then print “Yes” else print “No”.
SOLUTIONS:
Setter's Solution
using System;
using System.Collections.Generic;
class some
{
public static void Main()
{
string[]ss=Console.ReadLine().Split();
int n=int.Parse(ss[0]);
int m=int.Parse(ss[1]);
char[,]cc=new char[n,m];
int x=0;
int y=0;
int count=0;
for(int i=0;i<n;i++)
{
string s=Console.ReadLine();
for(int j=0;j<m;j++)
{
cc[i,j]=s[j];
if(s[j]=='X')
{
x=i;y=j;
}
if(s[j]=='K')
{
count++;
}
}
}
Queue<int>qq=new Queue<int>();
List<string>done=new List<string>();
qq.Enqueue(x);
qq.Enqueue(y);
done.Add(x+" "+y);
int[]dx={0,0,1,-1,-1,1,1,-1};
int[]dy={1,-1,0,0,1,-1,1,-1};
while(qq.Count>0)
{
int nx=qq.Dequeue();
int ny=qq.Dequeue();
for(int i=0;i<8;i++)
{
int nextx=nx+dx[i];
int nexty=ny+dy[i];
if(nextx>=0 && nextx<n && nexty>=0 && nexty<m)
{
if(cc[nextx,nexty]=='#')continue;
if(!done.Contains(nextx+" "+nexty))
{
done.Add(nextx+" "+nexty);
qq.Enqueue(nextx);
qq.Enqueue(nexty);
if(cc[nextx,nexty]=='K')
{
count--;
}
}
}
}
}
if(count==0)Console.WriteLine("Yes");
else Console.WriteLine("No");
}
}
ALTERNATE SOLUTIONS:
A flood fill should work, however haven’t tried.