Background

The input testdata for this problem contains \r\n; please use cin or scanf for input.

Problem Description

On a $4\times 4$ board there are $14$ pieces: $7$ white and $7$ black, with two empty cells. Any piece may move up, down, left, or right into an adjacent empty cell; this counts as one move. Black and white move alternately, and either side may move first. If at any time the pieces of either color form four in a line (including diagonals), that state is a target board position.

Input Format

Read a $4\times 4$ initial board from the file. Black pieces are denoted by B, white pieces by W, and empty cells by O.

Output Format

Output the minimum number of moves required to reach a target board position.

BWBO
WBWB
BWBW
WBWO

5

Hint

Translated by ChatGPT 5