Problem Statement
题目简述
一个 n * m 的矩形棋盘，有一些格子被ban掉了，
其余的每个格子你可以指定放或不放硬币。
放完硬币后你可以做若干次操作，
每次操作你可以指定一个方向（上下左右），
使所有的硬币尝试向那个方向移动一格。
如果一个硬币的目标格子被ban那么它不会移动。
硬币可以被移出棋盘（然后就掉在外面回不来了）。
一个格子上可以有多枚硬币。
求有多少种放硬币的方案，满足存在一种操作序列使至少有一枚硬币被移出棋盘、同时至少有一枚硬币留在棋盘上。
We are playing a game with some of coins on a rectangular board.
The board is divided into unit square cells.
Each cell is either empty, or it contains an obstacle.
The board is given to you as a String[] board.
The character '#' represents an obstacle and '.' is an empty cell.
When starting the game, the player places coins into some of the empty cells.
The number of coins and their positions are chosen by the player.
The only restriction is that the player may not place two coins into the same cell.
Next to the board, there are 4 buttons labeled "Left", "Right", "Up", and "Down".
The game is played by pushing these buttons.
When the player pushes a button, all coins will try to move one cell in the corresponding direction.
For each coin, there can be three different outcomes:
- If the next cell in the chosen direction contains an obstacle, the coin remains in its current cell.
- If there is no next cell in the chosen direction (i.e., if the coin is already on the corresponding edge of the board), the coin falls off the board.
- In all other cases, the coin moves one cell in the chosen direction. (Note that this includes the case when the destination cell currently contains another coin. In this way it may happen that there will be multiple coins in the same cell.)
The goal of the game is to make some coins (at least one) fall off the board, while some others (at least one) still remain on the board.
The initial configuration of coins is called good if there is a sequence of buttons that can be pushed to win the game from that configuration.
Return the number of good initial configurations, modulo 1,000,000,009.