The problem is a typical game theory problem. Let us denote by ~D~ the distance between ~A~'s and ~B~'s starting points. Both players have the same distance ~D~ to travel. Therefore, it is obvious that both players should move along a shortest path between starting points. Otherwise, a player would make at least ~D+1~ moves and his opponent would win. Since player ~A~ moves first, he will win if and only if player ~B~ is unable to reach the same square as player ~A~ in ~D/2~ moves. Hence, if ~D~ is odd, then ~A~ wins. So, from now on, we assume that ~D = 2d~.

Since players move along shortest paths, it is easy to find for each player, all such squares that can be reached in exactly ~p~ moves. We can do this by running the BFS algorithm twice and finding the distances from ~A~'s and ~B~'s starting points to all the squares. After ~p~ moves, player ~A~ can be on one of the squares whose distance to ~A~'s starting point is ~p~ and the distance to ~B~'s starting point is ~D-p~ (and conversely for player ~B~).

This basic observation is necessary to solve this problem correctly, as it gives us the order in which all configurations of ~A~'s and ~B~'s positions should be processed.

Model Solution

This solution uses simple dynamic programming. Let ~LA_k~ and ~LB_k~ be the lists of such squares which can be reached by players ~A~ and ~B~, respectively, in ~k~ moves, and can be reached by their respective opponent in ~D-k~ moves. By ~LA_k[i]~ and ~LB_k[i]~, we will denote the ~i^\text{th}~ elements of these lists. Let ~T_{k,i,j}~ be true if after ~d-k~ moves, player ~A~ has a winning strategy when his piece is on the square ~LA_{d-k}[i]~ and player ~B~ is on the square ~LB_{d-k}[j]~. If ~B~ has a winning strategy, then ~T_{k,i,j}~ is false. Please note that ~LA_d~ equals ~LB_d~, and ~T_{0,i,j}~ is true for all ~i~ and ~j~ such that ~LA_d[i] \ne LB_d[j]~ (that is, the pieces cannot stand on the same square).

Please note that ~A~ has a winning strategy, iff he can make such a move, after which ~B~ can only make moves, after which ~A~ still has a winning strategy. More formally, let ~NextA_{k,i}~ be the list of squares from ~LA_{d-k+1}~ onto which player ~A~ can move from ~LA_{d-k[i]}~. Let ~NextB_{k,j}~ be a similar list for player ~B~. If for some ~i' \in NextA_{k,i}~, for all ~j' \in NextB_{k,j}~ the value of ~T_{k-1,i',j'}~ is true, then ~T_{k,i,j}~ is true, otherwise it is false.

Using the above observation, we can calculate values ~T_{k,i,j}~ for ~k = 1, 2, \dots, d~. Player ~A~ has a winning strategy in the whole game if and only if ~T_{d,1,1}~ is true.

The only problem is to compute ~NextA~ and ~NextB~ lists efficiently. For square ~(x, y)~ where one of the players can be after ~k~ moves, we can easily find all squares ~(x', y')~ where this player can be after ~k+1~ moves. The problem is to find the position of ~(x', y')~ on the ~LA_{k+1}~ and ~LB_{k+1}~ lists. But since each square is present on at most two such lists, when we add some square to some list, we can also store its position on an appropriate list.

Since each value ~T_{k,i,j}~ can be computed in constant time, the total time complexity is ~\mathcal O(n^3)~. Please note that although there are ~\mathcal O(n^3)~ values ~T_{k,i,j}~, we only have to store ~T_{k,i,j}~ for two consecutive values of ~k~. Moreover, since each square belongs to at most two lists ~LA~/~LB~, these lists occupy ~\mathcal O(n^2)~ memory. Therefore, the overall memory complexity is ~\mathcal O(n^2)~.