plan, a list of equal-length strings. Each cell is one character:
- '.' is open floor;
- '#' is a wall;
- '@' is the robot's starting cell (also open floor);
- a lowercase letter is a key;
- an uppercase letter is a door, opened by the key with the same letter in lowercase.
In one step the robot moves to a neighboring cell up, down, left or right. It cannot leave the plan or enter a wall. Stepping onto a key picks it up, and the robot can pass through a door only once it holds that door's key. If there are k keys, they are exactly the first k letters of the alphabet, one of each. Several doors may share a letter, and a door whose key is not on the plan never opens.
Return the smallest number of steps the robot needs to collect every key. It does not have to open every door. If collecting all keys is impossible, return -1.plan=['@.a', '##A', 'b..'] → 6
Grab key a first (2 steps), then go down through the door A, one more cell down and 2 steps left to key b: 6 steps in total.
plan=['@#a', '.#.', '...'] → 6
The wall in the middle forces a detour along the bottom row: 6 steps to the key.
plan=['@Bb', '#Aa'] → -1
Both doors block the way out of the start and the keys lie behind them, so the answer is -1.
len(plan) ≤ 60, 1 ≤ len(plan[i]) ≤ 60, all rows have the same lengthplan[i][j] is a Latin letter, '.', '#' or '@''@' appears exactly onceplan=['@.a', '##A', 'b..']
6
Run checks the first 3 tests in your browser. Submit checks all 29 tests on the server, hidden ones included.