[COCI2019-2020#6] Skandi

题目翻译来自 [LOJ3269](https://loj.ac/problem/3269) 。 **由于洛谷评测机原因，数据有删改。**

**译自 [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 不仅是当地的一个半专业保龄球队的队长，还是一位充满激情的厨师。除此之外，他还是克罗地亚数一数二的填字游戏（crossword）玩家。填字游戏是一个在 $N\times M$ 的网格上游玩的游戏。在游戏开始前，部分格子已经填上了字母，作为至多两题的起点，而玩家需要根据给出的提示以水平向右或竖直向下的方向在剩下的格子填上答案。在这里，一题的答案定义为从该题起点沿提示指定方向直至网格边界或另一题起点之前的部分。如果一题的起点右边一格是空的，则该题在水平方向上存在一题；类似的，如果一题的下面一格是空的，则该题在竖直方向上存在一题。 Dragica 当然知道答案啦，但他有点鸽，想让你帮他找出完成某个填字游戏最少回答的题目数。

第一行两个空格分隔的整数 $N,~M$，含意见题目描述。 接下来 $N$ 行每行 $M$ 个字符 `0` 或 `1`，其中 `0` 表示这是个待填充答案的空格，而 `1` 表示该格已填有字符，是至多两题的起点。保证输入存在至少一个 `0` ，且第一行和第一列均为 `1`。

第一行输出完成该次填字游戏的最小答案数 $X$。 接下来 $X$ 行每行以 `r c dir` 的格式回答一个问题，其中 `r` 表示题目的行号，`c` 表示题目的列号，`dir` 为 `DESNO` （克罗地亚语中的右）和 `DOLJE` （克罗地亚语中的下）之一，表示 Dragica 回答问题的方向。 如果有多解，输出任意一个。

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

#### 样例 $3$ 解释： 下图展示了样例中的填词游戏，其中黑色的格子表示开始时已经填了字符的格子，在图下方所示的表中你可以看到给出的横着填和竖着填的提示。注意，已经填了字符的格子可以是零题、一题（例如第 $8$ 和 $13$ 题）或两题（例如第 $10$ 和 $12$）题的起点。要解出它，你至少需要知道 $14$ 题的答案，试试看看你会吗？~~（疑问语气）~~ *译者注：以下图片经过高清重制。中文的 crossword 没啥意义，就不翻译了。*   ----- #### 数据范围： 对于 $100\%$ 的数据，有 $2\le N,~M\le 500$。 各子任务限制见下表： |子任务|分值|特殊限制| |:-:|:-:|:-:| |1|16|至多 $9$ 个格子开始前填了字符| |2|30|$N\le 500,~M\le 10$| |3|54|无特殊限制|