P6220 [COCI 2019/2020 #6] Skandi

This problem is translated from [LOJ3269](https://loj.ac/problem/3269). **Due to issues with the Luogu judge, the testdata has been modified.**

**Translated from [COCI 2019/2020 Contest #6](https://hsin.hr/coci/archive/2019_2020/) T4.** ***[Skandi](https://hsin.hr/coci/archive/2019_2020/contest6_tasks.pdf)*** 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.

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`.

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.

#### 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: |Subtask|Points|Special constraints| |:-:|:-:|:-:| |1|16|At most $9$ cells contain letters before the start| |2|30|$N \le 500, M \le 10$| |3|54|No special constraints| Translated by ChatGPT 5