1250 - New Gobang

Time Limit : 1 Second

Memory Limit : 128 MB

Submission: 118

Solved: 26

Description
Xiao A and Xiao B are interested in the game Gobang (Wu Zi Qi). After many years of playing they are bored. So they decide to change the rules.
New rule:
1. Each round a player can place one or two pawns on the chess board. Two players place alternatively.
2. A player will win the game if exactly 6 of his pawns are aligned horizontally, vertically or diagonally first.
Now given a state, please analyze it and tell if A or B can win if it is his turn to place pawns.
Input
There are multiple cases ended with EOF. Every case is terminated with a blank line .
The first line of each case is two lines H, W(1 <= H, W <= 100). The height and width of the board.
Then H lines each with W characters.
‘.’ means blank grids.
‘A’ means Xiao A’s pawn.
‘B’ means Xiao B’s pawn.
Output
If none of them can win, output “None” .
If only Xiao A can win, output “A” .
If only Xiao B can win, output “B” .
If both of them can win, output “Both” .
sample input
3 3
…
…
…

1 6
AA.A.A

1 10
AAAA..BBBB
sample output
None
A
Both
hint
source
© 2015 HUST ACMICPC TEAM. All Right Reserved.