Recently i tried to solve the [Amazing Robots](https://ioinformatics.org/files/ioi2003problem5.pdf) task in IOI 2003.My first Idea was to run dijsktra while updating weights by calculating the position of guards. As we cannot wait in a position without a command this won't work. After that i have no idea how to solve this. ↵
↵
I googled for a solution and this is the only one i found from [here](https://www.iarcs.org.in/inoi/online-study-material/problems/amazing-robots-soln.php#solution) .↵
↵
↵
~~~~~↵
Do a BFS on the state space.↵
↵
Naive state space is↵
↵
Position of robots in each grid.↵
Position of each guard.↵
This is too large (state space is 400 × 400 × ....).↵
↵
Instead, compute the guards' positions as a function of time. In this case, we need to maintain:↵
↵
Position of robots in each grid.↵
Current time T.↵
State space is still 400 × 400 × N, where N is the number of steps till they get out, which may become too large.↵
↵
Observe that the guards' beats are of length 2, 3 or 4. Thus, each guard returns to his starting position after 2, 4 or 6 moves. Thus, we only need to keep track of time T modulo 2, 4 and 6. Since lcm(2,4,6) is 12, if we keep track of T modulo 12, we can recover all these three values.↵
↵
In this problem, it is important to recognize that the path lengths for the guards allow you to cut down the state space of the BFS dramatically, to bring it within limits. Also, the number of edges is small because each node has at most 4 neighbours, corresponding to the N-S-E-W moves.↵
~~~~~↵
↵
But i don't know what the State Space means. And i'm having hard time understanding how the BFS works. here. (Edit: I understand how a simple BFS works) Again i googled and searched here for the _state space of a BFS_ but found nothing.↵
↵
Can someone help me understand what State Space of a BFS means and how can we use it to Solve this problem.↵
↵
Thank you very much for your time.↵
↵
I googled for a solution and this is the only one i found from [here](https://www.iarcs.org.in/inoi/online-study-material/problems/amazing-robots-soln.php#solution) .↵
↵
↵
~~~~~↵
Do a BFS on the state space.↵
↵
Naive state space is↵
↵
Position of robots in each grid.↵
Position of each guard.↵
This is too large (state space is 400 × 400 × ....).↵
↵
Instead, compute the guards' positions as a function of time. In this case, we need to maintain:↵
↵
Position of robots in each grid.↵
Current time T.↵
State space is still 400 × 400 × N, where N is the number of steps till they get out, which may become too large.↵
↵
Observe that the guards' beats are of length 2, 3 or 4. Thus, each guard returns to his starting position after 2, 4 or 6 moves. Thus, we only need to keep track of time T modulo 2, 4 and 6. Since lcm(2,4,6) is 12, if we keep track of T modulo 12, we can recover all these three values.↵
↵
In this problem, it is important to recognize that the path lengths for the guards allow you to cut down the state space of the BFS dramatically, to bring it within limits. Also, the number of edges is small because each node has at most 4 neighbours, corresponding to the N-S-E-W moves.↵
~~~~~↵
↵
But i don't know what the State Space means. And i'm having hard time understanding how the BFS works
↵
Can someone help me understand what State Space of a BFS means and how can we use it to Solve this problem.↵
↵
Thank you very much for your time.↵
