Field Navigation
InterviewTime limit1sMemory limit1024 MB
Find the fewest tools to carry so you can walk from the start to the hat, where each tool clears one obstacle type (grass, branches, or rocks).
- Level
Easy3 of 10
- Topics
- BFS, Matrix, Brute force
- Solved
- No attempts yet
Problem
Your field has become quite cluttered, and you just realized you left your best hat out in the middle of the pasture. You have to go retrieve it before it stays out any longer than it already has, but you're also lazy. There are many obstacles in the way. You have a sickle to cut tall grass, an axe to chop up any wood in the way, and a hammer to destroy rocks you can't get through, but you don't want to carry them all. Given the location of your hat and the layout of the field and all the obstacles, determine the minimum number of tools you'll have to bring to reach your prized hat.
Input
The first line contains a single integer n, the number of data sets that follow. Each data set starts with a single integer s, the side length of your square field. The next s lines contain a map of your field. '.' is open space, 'X' is your hat, 'S' is your starting position leaving your house, 'R' is a rock, 'B' is a branch, and 'G' is tall grass. You can only move up, down, left, and right. No diagonals.
Output
For each test case, output the minimum number of tools needed to retrieve your hat.