Rooks

Time limit1sMemory limit128 MB

Summary
Given a 15x15 board of marked squares, find the minimum number of rooks needed so every marked square lies in a chosen row or column.
Level

Medium7 of 10

Topics
Greedy, Brute force, Bit manipulation, Implementation
Solved
No attempts yet

Problem

You have unexpectedly become the owner of a large chessboard, fifteen squares on each side. Because you do not know how to play chess on such a large board, you decide to make use of it another way.

In chess, a rook attacks every square in the same row or the same column as itself. For this problem, a rook also attacks the square it stands on. A rook may be placed on any square of the board.

Given a set of marked squares, how many rooks are needed to attack all of them?

Input

Input consists of a number of test cases. Each test case consists of fifteen lines, each containing fifteen characters describing the board. Each character is either a period (.) or a hash (#). Every square marked with a hash must be attacked by a rook. After all the test cases, one more line appears, containing the word END.

Output

Output exactly one line per test case, containing a single integer: the minimum number of rooks that must be placed on the board so that every hash-marked square is attacked.

Examples2

  1. Example 1

    Input
    ...............
...............
...............
...............
...............
...............
...............
.......#.......
...............
...............
...............
...............
...............
...............
...............
END
    Expected output
    1

  2. Example 2

    Input
    ###............
###............
###............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
END
    Expected output
    3