Flag Recognition

Interview

Time limit1sMemory limit128 MB

Summary
Given a 6x9 letter grid, compute the minimum edits needed to make it a valid three-stripe flag, either horizontal (2-row bands) or vertical (3-column bands) with the middle band's color differing from both outer bands.
Level

Easy3 of 10

Topics
Brute force, Implementation, Simulation
Solved
No attempts yet

Problem

Huiwon built a flag recognition system. The system filters a flag into a 6*9 matrix and then recognizes it. Each cell of the matrix contains an uppercase letter representing a color.

Because the system is still in an early stage, it can recognize only simple flags split into three parts, as shown below.

CCCCCCCCC     CCCCCCCCC     ZZZBBBCCC     ZZZAAAZZZ
CCCCCCCCC     CCCCCCCCC     ZZZBBBCCC     ZZZAAAZZZ
BBBBBBBBB     BBBBBBBBB     ZZZBBBCCC     ZZZAAAZZZ
BBBBBBBBB     BBBBBBBBB     ZZZBBBCCC     ZZZAAAZZZ
PPPPPPPPP     CCCCCCCCC     ZZZBBBCCC     ZZZAAAZZZ
PPPPPPPPP     CCCCCCCCC     ZZZBBBCCC     ZZZAAAZZZ

A simple flag is a 6*9 matrix split into three horizontal parts of 2 rows each, or into three vertical parts of 3 columns each, such that every cell in each part has the same color. The color of the middle part must be different from the colors of both outer parts. The two outer parts may have the same color or different colors.

Given a recognized flag, write a program that finds the minimum number of characters that must be changed to make it a simple flag.

Input

Six lines are given. Each line contains 9 uppercase English letters.

Output

Print the minimum number of characters that must be changed to make the flag simple.

Examples3

  1. Example 1

    Input
    CCCCCCCCC
CCCCCCCCC
CBBBBBBBC
PBBBBBBBP
PPPPPPPPP
PPPPPPPPP
    Expected output
    4

  2. Example 2

    Input
    AZZAAAMMA
AZZAAAMMA
ZZZAMAMMM
ZZZAAAMMM
AZZAAAMMA
AZZAAAMMA
    Expected output
    9

  3. Example 3

    Input
    TAAAOAAAT
AAAOAOAAA
OOOAAAOOO
OOOAAAOOO
AAAOAOAAA
TAAAOAAAT
    Expected output
    16