Under construction

Still being built. Things may change

Surrounding Chess Pieces

Time limit2sMemory limit2048 MB

Summary
Count the ways to place white pieces on an 8x8 board so that no two black pieces are connected through empty squares.
Level

Medium7 of 10

Topics
Dynamic programming, Bit manipulation, Matrix
Solved
No attempts yet

Problem

Chess is a game of strategy and intellect that has been played for centuries. It offers endless possibilities, and players can stay absorbed in a single game for hours. Suppose you have no opponent. Here is a puzzle instead.

You have an 8×88 \times 8 chessboard. You have up to 64 white pieces and up to 64 black pieces. Some black pieces are already on the board. Place white pieces so that no two black pieces are "connected".

Two black pieces are connected if you can move from one to the other through empty squares, one square at a time, moving horizontally or vertically. In other words, no path of empty squares may join two black pieces without passing through a white piece.

Write a program that counts the ways to place white pieces so that all black pieces are separated. All white pieces are indistinguishable.

Input

The input consists of 8 lines, each with 8 characters. A "." marks an empty square, and a "B" marks a square with a black piece.

Output

Print a single integer: the number of ways to place white pieces so that no two black pieces can reach each other.

Examples3

  1. Example 1

    Input
    .B.B.B.B
B.B.B.B.
.B.B.B.B
B.B.B.B.
.B.B.B.B
B.B.B.B.
.B.B.B.B
B.B.B.B.
    Expected output
    1

  2. Example 2

    Input
    B......B
........
........
........
........
........
........
B......B
    Expected output
    834135523322500070

  3. Example 3

    Input
    ........
........
........
........
........
........
........
BB......
    Expected output
    0