KQM17B - editorial

PROBLEM LINK:

Practice
Contest

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.