Otherworld Game
Time limit2sMemory limit128 MB
Find the minimum adjacent swaps on a 4x4 grid to transform a current P/L pattern into a target pattern.
- Level
Medium7 of 10
- Topics
- BFS, Brute force, Simulation
- Solved
- No attempts yet
Problem
Truck driver Taekhee was summoned to another world in recognition of his long service. In that world live the angel race Portableangel and the demon race Legnaelbatrop. Using his excellent algorithmic knowledge, Taekhee soon became the king who rules both races.
When Taekhee gets bored, he chooses 16 residents regardless of race and places them in a 4×4 grid. He then specifies which race must stand in each cell and orders the residents to rearrange themselves. In one swap, only two residents in cells sharing an edge may exchange places, and the same resident may be swapped multiple times.
Given the current arrangement and Taekhee's desired arrangement, find the minimum number of swaps needed to obtain the desired arrangement.
Input
Four strings of length 4 are given without spaces, and each character is either 'P' or 'L'. These strings describe the current arrangement: 'P' means Portableangel, and 'L' means Legnaelbatrop.
After zero or more blank lines, the desired arrangement is given in the same format. An impossible arrangement is never given.
Output
Print the minimum number of swaps needed to make the desired arrangement.