시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 8 | 2 | 2 | 25.000% |
Let's call a maze a rectangular field of cells, where cells can either be empty or contain a wall, and one can move from an empty cell to its empty neighbour cells in four directions.
Let's call a maze connected if it's possible to reach any its empty cell from any other empty cell by moving in four directions.
There was a connected maze of size $n \times m$. It was cyclically shifted some rows down and some columns right, but nobody knows the exact shifts. Find all possible shifts.
The first line contains two integers $n$ and $m$ ($1 \le n, m \le 200$) --- the sizes of maze.
Each of the next $n$ lines contains $m$ characters ".
" or "#
" --- empty cells and walls, correspondingly.
There is at least one empty cell in the maze.
In the first line output a single integer $k$ ($0 \le k \le n \cdot m$) --- the number of possible shifts.
In each of the next $k$ lines output two integers $r_i$ and $c_i$ ($0 \le r_i < n, 0 \le c_i < m$) --- the number of rows the original maze was shifted down and the number of columns it was shifted right. Pairs ($r_i$, $c_i$) should be output in lexicographical order. Original maze must be connected for each of these cases.
5 6 ..#### .###.. ...#.# ##...# .###..
9 0 2 0 3 0 4 1 2 1 3 1 4 4 2 4 3 4 4
8 10 ########## .......... #.####..## ..###..##. #....##... ######..## ....###... ....###...
2 0 5 1 5