BoardEscape

Alice and Bob have a rectangular board divided into a grid with r rows and c columns. The grid is described by the String[] s. Each character of s represents one cell. There are four types of cells:

• 'E' denotes an exit. There may be arbitrarily many exits, possibly zero.
• 'T' means the square contains a single token. There may be arbitrarily many tokens, possibly zero.
• '#' denotes an obstacle.
• '.' denotes an empty cell.

Alice and Bob will play a game on this board. The game is parameterized by the int k. Each token initially has the number k on it. The players will take alternating turns, starting with Alice. A player's turn consists of the following steps:

1. The player chooses a single token on the board and moves it one square up, down, left, or right. The token cannot go over the edge of the board and it cannot enter a cell with an obstacle. The token may be moved into a cell that already contains other token(s). During the game, arbitrarily many tokens may share the same cell.
2. If this token is on an exit, it disappears from the board.
3. Otherwise, subtract one from the number on the token. If the number on the token is zero, remove it from the board. (The numbers on other tokens do not change.)

The first player unable to make a move loses the game.

You are given the String[] s and the int k Compute the winner of the game, assuming both Alice and Bob play optimally. Return the winner's name: either "Alice" or "Bob".