We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
This problem is more straightforward than I think most (even the problem setter) realize.
Do a simple BFS or DFS to find the unique path from the start to the exit. Then, for each point in the path excluding the start and finish, count the number of neighbors. If the number of neighbors is more than 2, that's a fork, and you can add 1 to your running total. Finally, add another 1 if the start has more than 1 neighbor.
No backtracking or recursion. Just a BFS to find a path, then a linear pass over the path to count forks.
Count Luck
You are viewing a single comment's thread. Return to all comments →
This problem is more straightforward than I think most (even the problem setter) realize.
Do a simple BFS or DFS to find the unique path from the start to the exit. Then, for each point in the path excluding the start and finish, count the number of neighbors. If the number of neighbors is more than 2, that's a fork, and you can add 1 to your running total. Finally, add another 1 if the start has more than 1 neighbor.
No backtracking or recursion. Just a BFS to find a path, then a linear pass over the path to count forks.