Sokoban

Time limit2sMemory limit512 MB

Summary

Count the (player, box) start placements on a grid with walls and one target from which the box can be pushed onto the target.

Level: Medium7 of 10
Topics: BFS, Graph, Implementation
Solved: No attempts yet

Problem

Sokoban is a puzzle played on a board divided into square cells, with $M$ rows and $N$ columns. A single box sits on the board, and the goal is to push it onto the target cell by moving the player. Some cells are walls. The player, the box, and the target each occupy a cell that is not a wall. Neither the player nor the box can leave the board.

The following two operations are possible.

Choose one cell adjacent to the player that is not a wall and has no box, and move the player to that cell.
When the player and the box are adjacent, and the cell on the far side of the box from the player is not a wall, push the box into that cell. The player then moves to the cell the box was in.

Two cells are adjacent if they share an edge.

Below is an example. # is a wall, @ is the player, O is the box, X is the target, and . is an empty cell.

..#@.
.X.O.
##..#

From this state, the box can be moved to the target with these moves.

Move the player right.
Move the player down.
Move the box and the player left.
Move the box and the player left.

In the following state, the box cannot be moved to the target.

..#..
.X.O.
##.@#

Given the wall positions and the target of a board, count how many solvable Sokoban problems can be made by placing the player and the box. A solvable problem is one where some sequence of operations moves the box to the target. The player and the box must each be placed on a cell that is not a wall and not the target, and they must be on different cells.

Input

The first line contains two integers $M$ and $N$ , separated by a space. They are the number of rows and the number of columns of the board.

Each of the next $M$ lines contains $N$ characters. Each character is one of #, X, or . The character # is a wall, X is the target, and . is any other cell, including a possible starting position for the player or the box. The character X appears exactly once.

Output

Print one integer on a single line: the number of solvable Sokoban problems that can be made from the board.

Constraints

$1 \le M \le 1000$ (number of rows)
$1 \le N \le 1000$ (number of columns)

Examples3

Example 1
Input
```
3 5
..#..
.X...
##..#
```
Expected output
```
9
```
Example 2
Input
```
2 3
.X.
...
```
Expected output
```
0
```
Example 3
Input
```
4 7
.#.#.##
##.#..#
....X..
##.#...
```
Expected output
```
24
```