/* Main.java */
public class Main
{
	public static void main(String[] args)
	{
		State s = new State(2, 2);
		State.WinnerResult r = s.winner();
		java.util.Iterator<State> i = r.steps.iterator();
		while (i.hasNext())
		{
			System.out.println(i.next());
			System.out.println("====================");
		}
		if (r.winner > 0)
			System.out.println("A wins by " + r.winner);
		else if (r.winner == 0)
			System.out.println("Draw");
		else
			System.out.println("B wins by " + (-r.winner));
	}
}


/* State.java */
import java.util.*;
public class State implements Cloneable
{
	static Map<State,State> internTable = new HashMap<State,State>();
	
	//  2x2 edge indices:
	// +6+9+
	// 0 1 2
	// +7+A+
	// 3 4 5
	// +8+B+
	// ie across the rows for vertical edges, then down the columns for horizontal edges
	
	int width;
	int height;
	boolean[] edges;
	boolean playerBsTurn;
	public State(int width, int height)
	{
		this.width = width;
		this.height = height;
		edges = new boolean[width * (height + 1) + (width + 1) * height];
		Arrays.fill(edges, false);
		playerBsTurn = false;
	}
	public State(int width, int height, boolean[] edges, boolean playerBsTurn)
	{
		this.width = width;
		this.height = height;
		if (edges.length != (width * (height + 1) + (width + 1) * height))
			throw new IllegalArgumentException();
		this.edges = edges.clone();
		this.playerBsTurn = playerBsTurn;
	}
	
	public int hashCode()
	{
		return Arrays.hashCode(edges) ^ (width << 24) ^ (height << 16) ^ (playerBsTurn ? 194813 : 123108653);
	}
	public boolean equals(Object o)
	{
		if (!(o instanceof State))
			return false;
		return ((State)o).width == width && ((State)o).height == height && Arrays.equals(((State)o).edges, edges);
	}
	public State intern()
	{
		// based on String.intern()
		// basically so that if we reach the same State through different paths, we have the same node
		// and winnerCache below is useful.
		State s = internTable.get(this);
		if (s != null)
			return s;
		internTable.put(this, this);
			return this;
	}
	public Object clone()
	{
		try
		{
			
			State s = (State)super.clone();
			s.winnerCache = null;
			s.edges = edges.clone();
			return s;
		}
		catch (CloneNotSupportedException e)
		{
			return null;
		}
	}
	
	public class AddEdgeReturn
	{
		State nextState;
		int scoreDifference; // relative extra score for player A - ie negative for player B
	}
	public AddEdgeReturn addEdge(int n)
	{
		int x, y, a, b;
		AddEdgeReturn ret = new AddEdgeReturn();
		ret.nextState = (State)clone();
		ret.nextState.edges[n] = true;
		ret.nextState.playerBsTurn = !playerBsTurn;
		// see if this edge adds any squares
		if (n < (width + 1) * height)
		{
			// the edge is vertical
			x = n % (width + 1);
			y = n / (width + 1);
			a = (x - 1) * (height + 1) + y + (width + 1) * height;
			b = x * (height + 1) + y + (width + 1) * height;
			if (x > 0)
			{
				if (edges[n - 1] && edges[a] && edges[a + 1])
				{
					if (playerBsTurn)
						ret.scoreDifference--;
					else
						ret.scoreDifference++;
					ret.nextState.playerBsTurn = playerBsTurn;
				}
			}
			if (x < width)
			{
				if (edges[n + 1] && edges[b] && edges[b + 1])
				{
					if (playerBsTurn)
						ret.scoreDifference--;
					else
						ret.scoreDifference++;
					ret.nextState.playerBsTurn = playerBsTurn;
				}
			}
		}
		else
		{
			// the edge is horizontal
			y = (n - (width + 1) * height) % (height + 1);
			x = (n - (width + 1) * height) / (height + 1);
			a = x + (y - 1) * (width + 1);
			b = x + y * (width + 1);
			if (y > 0)
			{
				if (edges[n - 1] && edges[a] && edges[a + 1])
				{
					if (playerBsTurn)
						ret.scoreDifference--;
					else
						ret.scoreDifference++;
					ret.nextState.playerBsTurn = playerBsTurn;
				}
			}
			if (y < height)
			{
				if (edges[n + 1] && edges[b] && edges[b + 1])
				{
					if (playerBsTurn)
						ret.scoreDifference--;
					else
						ret.scoreDifference++;
					ret.nextState.playerBsTurn = playerBsTurn;
				}
			}
		}
		ret.nextState = ret.nextState.intern();
		return ret;
	}
	
	public String toString()
	{
		StringBuffer s = new StringBuffer();
		for (int y = 0; y <= height; y++)
		{
			for (int x = 0; x < width; x++)
			{
				s.append('\u00B7');
				if (edges[x * (height + 1) + y + (width + 1) * height])
					s.append('-');
				else
					s.append(' ');
			}
			s.append("\u00B7\n");
			if (y < height)
			{
				for (int x = 0; x <= width; x++)
				{
					if (edges[x + y * (width + 1)])
						s.append('|');
					else
						s.append(' ');
					if (x != width)
						s.append(' ');
				}
				s.append('\n');
			}
		}
		s.append(playerBsTurn ? 'B' : 'A').append(" to move");
		return s.toString();
	}
	
	// >0 if this is a win for A, 0 if it's a draw, <0 if it's a win for B
	// on player A's turn, >0 means any subnode is a >0, 0 means any subnode is a 0 (but none are >0), <0 means all subnodes are <0 - ie return the maximum
	// on player B's turn, vice-versa.
	// only consider what score we can earn from this point onward - this way we can cull duplicates based that differ only by the score to date.
	// unfortunately this means we cannot stop searching when we find a guaranteed win for the player, but instead search for the highest point difference.
	public static class WinnerResult
	{
		int winner;
		LinkedList<State> steps;
	}
	private WinnerResult winnerCache = null;
	public WinnerResult winner()
	{
		if (winnerCache != null)
			return winnerCache;
		winnerCache = new WinnerResult();
		// is this a final node? If so, we know the result is a draw already - this is the terminator for the recursion
		int i;
		for (i = 0; i < edges.length; i++)
			if (!edges[i])
				break;
		if (i >= edges.length)
		{
			// neither player can get any more points
			winnerCache.winner = 0;
			winnerCache.steps = new LinkedList<State>();
			winnerCache.steps.addFirst(this);
			return winnerCache;
		}
		// assume a loser until we can better the situation
		winnerCache.winner = playerBsTurn ? 9999 : -9999;
		for (i = 0; i < edges.length; i++)
		{
			if (edges[i])
				continue;
			AddEdgeReturn next = addEdge(i);
			WinnerResult ret = next.nextState.winner();
			int tmp = ret.winner + next.scoreDifference;
			if (playerBsTurn)
			{
				if (tmp < winnerCache.winner)
				{
					winnerCache.winner = tmp;
					winnerCache.steps = ret.steps;
				}
			}
			else
			{
				if (tmp > winnerCache.winner)
				{
					winnerCache.winner = tmp;
					winnerCache.steps = ret.steps;
				}
			}
		}
		winnerCache.steps = (LinkedList<State>)winnerCache.steps.clone();
		winnerCache.steps.addFirst(this);
		return winnerCache;
	}
}