P1263 [CEOI 2002] Royal guards

# Description Once upon a time there was a kingdom whose castle was a rectangle of $m$ rows and $n$ columns, divided into $m \times n$ cells. Some cells are walls, and others are empty. The king has set traps in the castle, each trap occupying one empty cell. One day, the king decided to deploy guards in the castle, and he wants to place as many guards as possible. The guards are strictly trained, so as soon as they find someone in the same row or the same column, they immediately shoot at that person. Therefore, the king wants to place the guards so that they cannot see each other, making it impossible for them to shoot one another. Guards can only be placed on empty cells, not on traps or walls, and at most one guard can be placed on any empty cell. If two guards are in the same row or column and there is no wall between them, they can see each other (guards move like rooks in chess). Your task is to write a program that, given the castle, computes the maximum number of guards that can be placed and outputs one optimal placement.

从前有一个王国，这个王国的城堡是 $m$ 行 $n$ 列的一个矩形，被分为 $m \times n$ 个方格。一些方格是墙，而另一些是空地。这个王国的国王在城堡里设了一些陷阱，每个陷阱占据一块空地。 一天，国王决定在城堡里布置守卫，他希望安排尽量多的守卫。 守卫们都是经过严格训练的，所以一旦他们发现同行或同列中有人的话，他们立即向那人射击。因此，国王希望能够合理地布置守卫，使他们互相之间不能看见，这样他们就不可能互相射击了。守卫们只能被布置在空地上，不能被布置在陷阱或墙上，且一块空地只能布置一个守卫。如果两个守卫在同一行或同一列，并且他们之间没有墙的话，他们就能互相看见。(守卫就像象棋里的车一样) 你的任务是写一个程序，根据给定的城堡，计算最多可布置多少个守卫，并设计出布置的方案。

第一行有两个整数 $m$ 和 $n$，表示城堡的规模。 第 $2$ 到第 $(m + 1)$ 行，每行 $n$ 个整数，第 $(i +1)$ 行第 $j$ 列的数 $a_{i, j}$ 表示城堡第 $i$ 行第 $j$ 列的方格的信息，其中 $0$ 表示空地，$1$ 表示陷阱，$2$ 表示墙。

This problem uses Special Judge. First output a single integer $k$, the maximum number of guards that can be placed. Then output $k$ lines. Each line contains two integers $x, y$, indicating that a guard is placed at row $x$ and column $y$.

Explanation for sample input and output 1: As shown in the figure (black cells are walls, white cells are empty, circles are traps, and G denotes a guard).  Constraints: For all testdata, it is guaranteed that $1 \leq m, n \leq 200$ and $0 \leq a_{i, j} \leq 2$. Translated by ChatGPT 5