1250 - New Gobang

Time Limit: 1s Memory Limit: 128MB

Submissions: 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