#include #include #include #include /* coordinates: [row][col] */ int present[8*8]; #define POS( r, c ) (((r) << 3)+(c)) /* p1 always < p2 */ int visited[8*8][8*8]; bool bob( int p1, int p2 ); inline bool wins(int p1, int p2) { int x = p1 >> 3, y = p1 &7, X = p2 >> 3, Y=p2&7; if (abs(x-X) == 1 && y == Y) return true; if (abs(y-Y) == 1 && x == X) return true; return false; } bool alice( int p1, int p2 ) { visited[p1][p2] = 1; visited[p2][p1] = 1; if (wins(p1,p2)) return true; for (int pass = 0; pass < 2; ++pass ) { int p = pass ? p1 : p2; int other = pass ? p2 : p1; /* up */ if ((p > 7) && present[p-8] && !visited[p-8][other]) if (bob(p-8,other)) return true; /* down */ if ((p < 56) && present[p+8] && !visited[p+8][other]) if (bob(p+8,other)) return true; /* left */ if ((p & 7) && present[p-1] && !visited[p-1][other]) if (bob(p-1,other)) return true; /* right */ if (((p&7) != 7) && present[p+1] && !visited[p+1][other]) if (bob(p+1,other)) return true; } visited[p1][p2] = 0; visited[p2][p1] = 0; return false; } bool bob( int p1, int p2 ) { visited[p1][p2] = 1; visited[p2][p1] = 1; if (wins(p1,p2)) return false; for (int pass = 0; pass < 2; ++pass ) { int p = pass ? p1 : p2; int other = pass ? p2 : p1; /* up */ if ((p > 7) && present[p-8] && !visited[p-8][other]) if (!alice(p-8,other)) return false; /* down */ if ((p < 56) && present[p+8] && !visited[p+8][other]) if (!alice(p+8,other)) return false; /* left */ if ((p & 7) && present[p-1] && !visited[p-1][other]) if (!alice(p-1,other)) return false; /* right */ if (((p&7) != 7) && present[p+1] && !visited[p+1][other]) if (!alice(p+1,other)) return false; } visited[p1][p2] = 0; visited[p2][p1] = 0; return true; } int main() { /* p1 always < p2 */ int p1, p2; int m, n, r, c; char line[100]; while (scanf("%d %d\n", &m, &n) == 2) { memset( present, 0, sizeof(present) ); memset( visited, 0, sizeof(visited) ); p1 = p2 = -1; for ( r = 0; r < m; ++r ) { gets(line); for ( c = 0; line[c]; ++c ) switch (line[c]) { case 'P': if (p1 == -1) p1 = POS( r, c ); else p2 = POS( r, c ); /* fall-through */ case '.': present[POS(r,c)] = 1; } } if (alice(p1,p2)) puts("Alice wins."); else puts("Bob wins."); } return 0; }