Connect Four Cheater
In Connect Four, there is a grid which sits vertically and has 7 columns (numbered 1 to 7 from left to right) and 6 rows. Connect Four is a two player game: one player is red, and the other is blue. The players take turn placing a piece of their colour into one of the columns, where it falls down until it hits the bottom of the board, or another piece. You cannot place a piece in a column if it already has 6 pieces in it. A player wins when they have 4 pieces of their colour in consecutive positions ("4 in a row") either vertically, horizontally or diagonally.
You and your friend are playing a game of Connect Four, where you are red and your friend is blue. Your friend has gone to the bathroom and you want to take this opportunity to make several moves (only with your red pieces) so that you have 4 in a row. To make it look less suspicious, you wish to perform the smallest possible number of moves which results in you winning.
Input Format
There are 6 lines of input, each with 7 characters, describing the initial state of the Connect Four board.
Each character is either R
(meaning your piece), B
(meaning your opponent's piece) or .
(meaning an empty cell).
Constraints
For all test cases:
- You are guaranteed that neither player has won the game yet.
- You are guaranteed all pieces are either at the bottom of their column, or on top of another piece (i.e. there are no floating pieces).
- You and your friend both regularly cheat, so there is no guarantee that you have both played the same number of pieces.
Additionally:
- For test cases worth 50%, it is possible to win in one move.
Output Format
Output a single line, a sequence of moves of minimum length which results in you winning. If there are multiple such sequences, you can output any of them.
If there is no way you can win, instead output the single integer -1
.
Sample Input 0
.......
.......
...R...
...B...
..BRR..
.BRBRBR
Sample Output 0
5 5
Explanation 0
There are multiple ways to win in two moves. These include:
- Placing in column 5 then column 6 (making 4 in a row diagonally).
- Placing in column 5 twice (making 4 in a row vertically).
- Placing in column 6 then column 7 (making 4 in a row horizontally).
Sample Input 1
.......
.......
.......
.......
.......
.......
Sample Output 1
1 1 1 1
Explanation 1
The board is empty and you can win by either placing 4 pieces in one column, or placing 1 piece in 4 adjacent columns.
Sample Input 2
...B...
RRBBRRB
BBRRBBR
RRBBRRB
BBRRBBR
RRBBRRB
Sample Output 2
-1
Explanation 2
There is no way to win, regardless of how many pieces you place.
xxxxxxxxxx
with Ada.Text_IO, Ada.Integer_Text_IO;
use Ada;
procedure Solution is
-- Enter your code here. Read input from STDIN. Print output to STDOUT
end Solution