PROBLEM LINK:
Author: Chandan Boruah
Tester: Chandan Boruah
Editorialist: Chandan Boruah
DIFFICULTY:
MEDIUM
PREREQUISITES:
Maths
PROBLEM:
Given a graph and a starting point, you need to find count of ways in which all unvisited nodes are visited such that the path is different in each way.
QUICK EXPLANATION:
This problem can be solved by multiplying the positions where there are multiple ways to traverse the path, and multiplying the count of such paths.
EXPLANATION:
You have find the count of unique paths with which all nodes can be visited from where he starts. This problem can be solved by counting the number of positions in the path where he has to make a decision between different directions. Multiplying all these directions will give the right answer. How?
Lets say you have to travel to a place and you have crossroads, which leads to the same place. How many ways can you reach that place. Of course the product of count of roads in the crossroads leading to that place!
Technically, this problem can be done by doing a graph traversal using dfs or bfs (read more about it here) and whenever in any position you have more than one way to move increase counter by 1 for that node. Save already visited nodes in a list and you can thus uniquely count the counters that are greater than 1. And then multiplying all such counters.
using System;
using System.Collections.Generic;
class some
{
public static void Main()
{
int n=Int32.Parse(Console.ReadLine());
for(int t=0;t<n;t++)
{
string[]ss=Console.ReadLine().Split();
int x=int.Parse(ss[0]);
int y=int.Parse(ss[1]);
int[,]arr=new int[x,y];
int startx=0-1;int starty=0-1;
for(int i=0;i<x;i++)
{
string p=Console.ReadLine();
for(int j=0;j<y;j++)
{
arr[i,j]=int.Parse(p[j]+"");
if(arr[i,j]==0 && startx==-1)
{
startx=i;starty=j;
}
}
}
Queue<int>qq=new Queue<int>();
qq.Enqueue(startx);
qq.Enqueue(starty);
List<string>done=new List<string>();
List<int> count=new List<int>();
done.Add(startx+" "+starty);
int[]dx={0,0,1,-1};
int[]dy={1,-1,0,0};
while(qq.Count>0)
{
int x1=qq.Dequeue();
int y1=qq.Dequeue();
int cc=0;
for(int i=0;i<4;i++)
{
int xx=x1+dx[i];int yy=y1+dy[i];
if(xx>=0 && xx<x && yy>=0 && yy<y)
{
if(arr[xx,yy]==0)
if(!done.Contains(xx+" "+yy))
{
done.Add(xx+" "+yy);
qq.Enqueue(xx);
qq.Enqueue(yy);
cc++;
}
}
}
if(cc<=1)continue;
count.Add(cc);
}
int ret=1;
foreach(int ii in count){ret*=ii;}
Console.WriteLine(ret);
}
}
}
The code is self explanatory, if I am not clear I shall edit.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found above.
Tester’s solution can be found above.