Hi Team, I recently solved SPOJ HERDING, using bfs approach by calculating the number of connecting components using 2D matrix method, but I am getting the wrong answer for some test cases.I figured out some of them which are:
4 4
SWWW
SEEW
SSWS
NNWN
Here is link to my code.If anyone can help…that’s would be great.
Take the example that you have given:
4 4
SWWW
SEEW
SSWS
NNWN
All the positions that I have written in bold must fall under one ‘component’, but that doesn’t happen in your code. Because your program will first go through the first column, mark all the positions as visited, and then, even though there is W at (0,1), it will not be able to visit (0,0). What you need to find in this problem is the number of ‘Weakly connected components’, in the given directed graph. A weakly connected component in a directed graph is a set of vertices such that for every pair of vertices (u,v), either ‘u’ can reach ‘v’ or ‘v’ can reach ‘u’. You can find this by ignoring the direction in your graph and then running dfs. I made these changes to your program (commented wherever I made changes) and it got accepted. Here’s the link:
okk…I got it!