A: Block Game
This problem had a fairly standard solution, but there was some tricky bookkeeping, which is probably why so few teams solved it. It particular, there were two issues that caught teams.
First, a lot of teams didn’t reset the board correctly when moving pieces. For example, suppose that both pieces A and B can move. Some teams wrote programs that would move piece A all the ways it could move, but would forget to put it back where it started before trying to move piece B.
The other catch was a little more tricky. A lot of teams wrote code that checked to see if the special piece could be moved all the way to the right. They figured that if you could move it there, you could just keep moving it and slide it out. And, most of the time, they would be right – but what if the special piece starts out all the way on the right side of the board? A lot of teams would answer 0 – that is, 0 moves. That’s incorrect. It always takes at least 1 move to remove the special piece.
Check out the Judge Input, the Judge Output, the main Solving Program, another solution, and another.
Join me in the spoiler for an outline of a solution.
[spoiler]
It’s just a breadth-first search. Despite the small size of the board and the limitations on how pieces move, the search space can still get quite large, so if you tried to use Depth-First Search (that is, you tried to solve it recursively) you probably ran out of time.
Create a queue of states. Each state has a board, and a number of moves. Start by putting a state on the queue that has the starting position, with 0 moves.
Each time you take a state off of the queue, check to see if the special piece is all the way to the right. If so, remember the number of moves, and exit the loop. Otherwise, generate all possible boards that can be attained in 1 move. For each, check to see if it’s been seen before, and if not, put it on the queue with a number of moves equal to this state’s number of moves plus one.
When you’re done, output the number of moves remembered, unless it’s 0, in which case output 1, or if you emptied the queue without reaching a solved state, output -1.
Sounds simple in paragraph form, but it’s not necessarily easy to generate all of the possible moves – remember, a lot of teams didn’t reset the board correctly. Also, remembering previously seen board positions is important, otherwise you’ll run out of time and memory.
[/spoiler]