Casino#2993
In the top-left corner of a rectangular field with dimensions N \times M, a die is placed. The unfolded view of the die is shown in the figure. Initially, the die is positioned so that the front face displays a one, and the left face shows a two. The field is composed of square cells, each matching the size of the die's face.
The die can move across the field by rolling over one of its edges, landing in an adjacent cell either below, above, to the right, or to the left. For instance, if the die rolls to the right from its starting position, the front face will show a two, and if it rolls downward, it will show a three. The die must remain within the boundaries of the field.
Your task is to write a program named CASINO that, given the field's layout, determines one possible path for the die from the top-left corner to the bottom-right corner. The goal is to ensure that the front face of the die displays the highest possible value when it reaches the final cell. The die is allowed to visit each cell multiple times.
The first line of the input contains two natural numbers and (2 \le N, M \le 50), representing the height and width of the field, respectively. The field is described by rows, each containing numbers, either or . A cell marked with is off-limits for the die, while a cell marked with can be included in the die's path. The starting cell is always marked with .
The first line of the output should contain a natural number — the length of the discovered path. Following this, the output should include lines, each indicating the coordinates of a field cell at each step. The coordinates are given as a pair of natural numbers: the row number and the column number of the cell.
If no valid path exists, the output should consist of a single line with the number .
مثال 1