Description

Translated from COCI 2019/2020 Contest #6 T4. Skandi

Dragica is not only the captain of a local semi-professional bowling team, but also a passionate cook. Besides that, he is also one of Croatia’s top crossword players. A crossword is played on an $N \times M$ grid. Before the game starts, some cells already contain letters, serving as the starting points of up to two clues, and the player needs to fill the remaining cells with answers according to the given clues, either horizontally to the right or vertically downward. Here, the answer to one clue is defined as the segment starting from the clue’s starting point and continuing in the indicated direction until reaching the grid boundary or the starting point of another clue. If the cell to the right of a starting point is empty, then there is a horizontal clue starting there; similarly, if the cell below a starting point is empty, then there is a vertical clue starting there.

Dragica of course knows all the answers, but he is a bit lazy and wants you to help him find the minimum number of clues that must be answered to complete a given crossword.

Input Format

The first line contains two space-separated integers $N, M$, as described above.

The next $N$ lines each contain $M$ characters, either 0 or 1. 0 means this cell is empty and needs to be filled with an answer, while 1 means this cell already contains a letter and is the starting point of up to two clues. It is guaranteed that there is at least one 0, and that the first row and the first column are all 1.

Output Format

On the first line, output the minimum number of answers needed to complete this crossword, $X$.

Then output $X$ lines, each answering one clue in the format r c dir, where r is the row number of the clue’s starting cell, c is the column number of the clue’s starting cell, and dir is one of DESNO (Croatian for “right”) and DOLJE (Croatian for “down”), indicating the direction in which Dragica answers the clue.

If there are multiple solutions, output any one of them.

4 5
11111
10000
10000
10000

3
2 1 DESNO
3 1 DESNO
4 1 DESNO

6 4
1111
1011
1000
1011
1010
1000

4
1 2 DOLJE
4 4 DOLJE
5 3 DOLJE
3 1 DESNO

9 8
11111111
10000000
10001000
10010001
11100001
10100110
10001000
10100001
10010001

14
5 2 DOLJE
5 8 DOLJE
8 3 DOLJE
2 1 DESNO
3 1 DESNO
3 5 DESNO
4 1 DESNO
4 4 DESNO
5 3 DESNO
6 3 DESNO
7 1 DESNO
7 5 DESNO
8 3 DESNO
9 4 DESNO

Hint

Explanation for Sample $3$.

The figure below shows the crossword in the sample, where the black cells are those that already contain letters at the start. In the table shown below the figure, you can see the given across and down clues. Note that a cell that already contains a letter can be the starting point of zero clues, one clue (e.g. clues $8$ and $13$), or two clues (e.g. clues $10$ and $12$). To solve it, you need to know at least the answer to clue $14$. Try to see if you can do it? (questioning tone)

Translator’s note: The following images have been remade in high resolution. The Chinese term for crossword does not make much sense, so it is left untranslated.

Constraints:

For $100\%$ of the testdata, $2 \le N, M \le 500$.

The limits for each subtask are shown in the table below:

Translated by ChatGPT 5