9-Puzzle

Time limit2sMemory limit512 MB

Summary

Given two configurations of a triangular 9-puzzle with one empty cell and four colors, find the fewest piece repaints that make the target reachable.

Level: Medium7 of 10
Topics: Graph, BFS, Bit manipulation, Brute force
Solved: No attempts yet

Problem

Youngsun's user ID is nein, because she likes the number 9. Why nein? When she made the ID, she thought nein was the English word for 9.

Youngsun likes 9, so she made a game called the 9-puzzle. It is played on a board shaped like an equilateral triangle with side length 4. The board has 10 cells, and each cell is an equilateral triangle with side length 1. The cells are numbered 0 to 9 as shown below.

Nine of the cells each hold one triangular piece. Each piece is red, green, blue, or yellow. The remaining cell is empty. The goal of the game is to form a given pattern. To do so, Youngsun moves a piece into an adjacent empty cell. Two cells are adjacent if the distance between their centers is 1. The figure below shows one valid move.

You are given the current state of the pieces and the state Youngsun wants to reach. Both states were chosen at random, so the game may be unsolvable. Write a program that finds the minimum number of pieces that must be repainted so that the game becomes solvable.

Input

The first line contains the current state, and the second line contains the target state. Each state is a string of length 10, and its $i$ -th character is the color of cell $i$ ( $0 \le i \le 9$ ). R is red, G is green, B is blue, Y is yellow, and * is the empty cell. Each state has exactly one empty cell.

Output

Print the minimum number of pieces that must be repainted so that the puzzle can be solved.

Hint

The first example can be solved as follows.

Examples3

Example 1
Input
```
BG*YRGRRYR
BGGY*YRRRR
```
Expected output
```
0
```
Example 2
Input
```
GBBB*BGBBG
RYYY*YRYYR
```
Expected output
```
9
```
Example 3
Input
```
RRBR*BRBBB
BBRB*RBRRR
```
Expected output
```
1
```