레이팅 미적용A sliding puzzle consists of square tiles on a rectangular grid. Exactly one of the grid positions is empty, so that you can move the tile above, below, to its left, or to its right into the empty square and back.
Each tile is labelled with a unique number, as shown in Figure . To solve a sliding puzzle, you need to find a sequence of moves that puts the tile numbers in ascending order, from left to right and top to bottom, such that the empty square ends up at the bottom right position in the grid, as shown in Figure . Such a sequence of moves does not exist for all sliding puzzles.
width=
width=
width=
While cleaning out your garage, you grapple with the garage goblins over a glowing box full of goodies. They offer a gamble: the box is yours if you can solve all their sliding puzzles. You accept to give it a go, only to find out that the garage goblins have glued some tiles in place! The glued tiles no longer move, as shown in Figure .
However, all sliding puzzles share the following properties:
- The empty square is at the bottom right position.
- Every glued tile is in its correct position.
- For each tile that can move, there is a sequence of moves that leaves the empty square in its position instead.
- From any glued tile, there is a path to the border of the sliding puzzle across glued tiles only, when stepping to the tile above, below, to the left, or to the right at each step. That is, no glued tiles are encircled by tiles that can move.
Determine whether it is possible to solve a given sliding puzzle.
The input consists of:
- One line with two integers \(h\) and \(w\) (\(1 \le h,w \le 500\)), the height and width of the sliding puzzle's grid.
- \(h\) lines with \(w\) characters, each character being either '.' or '#'. The bottom right character, at the position of the empty square, is '.'. Otherwise, '.' denotes a tile that can move, and '#' denotes a glued tile.
- \(h\) lines with \(w\) integers \(a_{i,j}\) (\(1 \le i \le h\), \(1 \le j \le w\), \(0 \le a_{i,j} \le h \cdot w - 1\)). The bottom right integer is \(a_{h,w} = 0\), representing the empty square. Otherwise, \(a_{i,j}\) is the label on the tile at position \((i,j)\).
The set of all \(a_{i,j}\) (\(1 \le i \le h, 1 \le j \le w\)) contains each of the numbers \(0, 1, \dots, h \cdot w - 1\) once.
Output possible if the sliding puzzle can be solved, or impossible if not.
3 4
....
....
....
10 8 2 3
6 7 5 9
11 1 4 0
possible
2 4
....
....
2 1 3 4
5 6 7 0
impossible
3 4
..#.
....
#...
5 1 3 4
2 6 7 8
9 10 11 0
possible
3 4
..#.
....
#...
7 1 3 4
5 6 2 8
9 10 11 0
impossible