Dots and Boxes

dotsandboxes.cc

#include<iostream>
using namespace std;

#define odd(x) (x&1)
#define even(x) (!(x&1))

int main(){

	int x;
	cin >> x;
	int n =11;
	int a[n][n];
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			cin >> a[i][j];
	for(int i=n-1;i>=0;i--)
		for(int j=n-1;j>=0;j--){
			int tmp = a[i][j];
			if((odd(i) && even(j)) || (even(i) && odd(j)))
				if(tmp == 0){
					cout << i << " " << j << "\n";
					return 0;
				}
		}
	cout << "0 1\n";
	return 0;
	
}

Interviewstreet's question:

Dots And Boxes

Dots and Boxes http://en.wikipedia.org/wiki/Dots_and_Boxes is a paper and pencil game played between two players. You probably played this game back in middle school. Now it's time to revisit it with your college-level intellect.

For the few of you unfamiliar with it, here's the 4 sentence rules of the game:

Starting with an empty grid of dots, players take turns, adding a single horizontal or vertical line between two unjoined adjacent dots.
A player who completes the fourth side of a 1x1 box earns one or two points depending on how many 1x1 boxes are completed by that side, and takes another turn
The game ends when no more lines can be placed.
The winner of the game is the player with the most points.

Your goal is to code a winning Dots and Boxes strategy.

If you are a complete beginner to Game AI, we recommend Intro to AI Techniques: Game Search, Minimax, and Alpha Beta Pruning (PDF), a lecture note from MIT OpenCourseware. It provides a good, not-too-brief overview of well established AI principles.

Board Representation

A 3x3 Dots&Boxes board is represented as - :

i.e a 7x7 matrix and as you might have guessed for a general nxn Dots&Boxes, a (2_n+1) x (2_n+1) matrix is needed.

For a cell (x, y) in the matrix the mappings are -
(odd, odd) - boxes
(even, even) - dots ( place where the lines intersect )
(odd, even) - vertical lines
(even, odd) - horizontal lines

The cells representing the lines have either 0 or 1. 0 means that this line is not taken by any of the players and 1 means that one of the players has taken this line.

The cells for boxes have either 0, 1 or 2. 0 indicating it belongs to none of the players. 1 means player1 has this box and 2 meaning it belongs to player2.

As an illustration in the above board, A and B are the first two boxes. If a player wants to join the vertical line to left of the box at coordinate (5, 5) he will put a 1 at (5, 4).

The board against which your program is run is 5x5 and thus a matrix of 11x11.

As an illustration if this is the board's matrix state at some point of the play :

0 1 0 1 0 0 0 0 0 0 0
1 2 1 2 1 0 0 0 0 0 1
0 1 0 1 0 0 0 0 0 0 0
0 0 1 1 1 0 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 1 0

First two boxes belong to player2 and player1 has the last( bottom-right most ) box and the box at coordinate( 3, 3 ). Also in the board 7 horizontal lines and 8 vertical lines are there.

Input Format

The first line of the input contains P, the name of player.
Then follows 11 lines, each of these lines contain 11 space separated integers. The ith line is the ith row of the matrix.

Output Format

Print to standard output in a single line, two space separated integers, x y. This means you want to join the line represented by cell ( x, y ). Only print a single pair of integers: If your move completes a box, the codechecker will call your function again for your next move.

Sample Game

The sample cases shown below represents one possible sequence of game runs.

Sample Input

2
0 1 0 1 0 0 0 0 0 0 0
1 2 1 2 1 0 0 0 0 0 1
0 1 0 1 0 0 0 0 0 0 0
0 0 1 1 1 0 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 1 0

Sample Output

0 9

Sample Input

1
0 1 0 1 0 0 0 0 0 1 0
1 2 1 2 1 0 0 0 0 0 1
0 1 0 1 0 0 0 0 0 0 0
0 0 1 1 1 0 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 1 0

Sample Output

2 9

Sample Input

2
0 1 0 1 0 0 0 0 0 1 0
1 2 1 2 1 0 0 0 0 0 1
0 1 0 1 0 0 0 0 0 1 0
0 0 1 1 1 0 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 1 0

Sample Output

1 8

Sample Input

2
0 1 0 1 0 0 0 0 0 1 0
1 2 1 2 1 0 0 0 1 2 1
0 1 0 1 0 0 0 0 0 1 0
0 0 1 1 1 0 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 1 0

Sample Output

4 5