HERDING - Herding is an easy DSU problem. If you are not familiar with term DSU, I suggest you to first of all understand DSU, then try solving this problem.
In this problem, we are give a n*m array and each block of array contains 'N','S','W' or 'E'. 'N' is for north, 'S' for south, 'W' for west and 'E' for east, and they represents the direction of movement of cat if it is on that block.
So, if a cat is present on a block, there is a specific path, which it will follow. If we keep trap at the end of that path, and cat is present anywhere in the path, it will end up in the trap!
So, all we need to do is to find the number of paths, which do not intersect at any point. And we will set traps at the end of every path.
For example:
There are two paths, one is shown by yellow color and second one by blue.
If we set a trap at any of the yellow block, then all cats which are at yellow path, will end up in that trap, and same for the blue path!
The thing you should notice is, there is only one way possible from each block. So, if we traverse whole n*m map, and connect each block to the next block (according to the given direction), we can find all paths!
So, our answer will be the number of disjoint paths!
Easy, isn't it? Now try implementing this code bye yourself or refer to the following code:
In this problem, we are give a n*m array and each block of array contains 'N','S','W' or 'E'. 'N' is for north, 'S' for south, 'W' for west and 'E' for east, and they represents the direction of movement of cat if it is on that block.
So, if a cat is present on a block, there is a specific path, which it will follow. If we keep trap at the end of that path, and cat is present anywhere in the path, it will end up in the trap!
So, all we need to do is to find the number of paths, which do not intersect at any point. And we will set traps at the end of every path.
For example:
Input: 3 4 SWWW SEWN EEEN Output: 2
There are two paths, one is shown by yellow color and second one by blue.
If we set a trap at any of the yellow block, then all cats which are at yellow path, will end up in that trap, and same for the blue path!
The thing you should notice is, there is only one way possible from each block. So, if we traverse whole n*m map, and connect each block to the next block (according to the given direction), we can find all paths!
So, our answer will be the number of disjoint paths!
Easy, isn't it? Now try implementing this code bye yourself or refer to the following code:
0 comments:
Post a Comment