Under construction

Still being built. Things may change

Omok: Can Kyusagwa Win?

Interview

Time limit2sMemory limit512 MB

Summary
On a 10x10 omok board, decide whether Kyusagwa, moving next with X stones, can place one stone to make five in a row.
Level

Medium4 of 10

Topics
Implementation, Simulation, Brute force, Array
Solved
No attempts yet

Problem

Kyusagwa and Qubelover are playing omok on a 10×10 board. Kyusagwa takes the first turn. The state of the board is given. Write a program to determine whether Kyusagwa can win if he takes one more turn.

Winning at omok means having 5 or more of your own stones in a row. The row can be horizontal, vertical, or diagonal.

Input

The state of the board is given over 10 lines. '.' is an empty cell, 'X' is Kyusagwa's stone, and 'O' is Qubelover's stone.

In the given board, the number of Kyusagwa's stones and the number of Qubelover's stones are always equal, and only states where the winner is not yet decided are given as input.

Output

Output 1 if Kyusagwa can win by taking one turn, and 0 otherwise.

Examples2

  1. Example 1

    Input
    XX.XX.....
.....OOOO.
..........
..........
..........
..........
..........
..........
..........
..........
    Expected output
    1

  2. Example 2

    Input
    XXOXX.....
OO.O......
..........
..........
..........
..........
..........
..........
..........
..........
    Expected output
    0