[CEOI2002] Royal guards
题目描述
从前有一个王国,这个王国的城堡是 $m$ 行 $n$ 列的一个矩形,被分为 $m \times n$ 个方格。一些方格是墙,而另一些是空地。这个王国的国王在城堡里设了一些陷阱,每个陷阱占据一块空地。
一天,国王决定在城堡里布置守卫,他希望安排尽量多的守卫。
守卫们都是经过严格训练的,所以一旦他们发现同行或同列中有人的话,他们立即向那人射击。因此,国王希望能够合理地布置守卫,使他们互相之间不能看见,这样他们就不可能互相射击了。守卫们只能被布置在空地上,不能被布置在陷阱或墙上,且一块空地只能布置一个守卫。如果两个守卫在同一行或同一列,并且他们之间没有墙的话,他们就能互相看见。(守卫就像象棋里的车一样)
你的任务是写一个程序,根据给定的城堡,计算最多可布置多少个守卫,并设计出布置的方案。
输入输出格式
输入格式
第一行有两个整数 $m$ 和 $n$,表示城堡的规模。
第 $2$ 到第 $(m + 1)$ 行,每行 $n$ 个整数,第 $(i +1)$ 行第 $j$ 列的数 $a_{i, j}$ 表示城堡第 $i$ 行第 $j$ 列的方格的信息,其中 $0$ 表示空地,$1$ 表示陷阱,$2$ 表示墙。
输出格式
**本题存在 Special Judge**。
首先输出一行一个整数 $k$,表示最多可布置的守卫个数。
然后输出 $k$ 行,每行两个整数 $x, y$,表示在第 $x$ 行第 $j$ 列放一个守卫。
输入输出样例
输入样例 #1
3 4
2 0 0 0
2 2 2 1
0 1 0 2
输出样例 #1
2
1 2
3 3
说明
#### 样例输入输出 1 解释
如图(黑色方格为墙,白色方格为空地,圆圈为陷阱,G表示守卫)
![](https://cdn.luogu.com.cn/upload/image_hosting/zv6sr9xw.png)
#### 数据规模与约定
对于全部的测试点,保证 $1 \leq m, n \leq 200$,$0 \leq a_{i, j} \leq 2$。