题目描述(ID:12096)
标题: 皇家保卫
标签:
详情: 从前有一个王国,它有所有王国应该有的,国王和他的城堡。城堡的平面图是一个矩形,被划分成M × N块单位正方形。一些块是墙,一些是空的。我们成一个空的块为房间。我们王国的国王是个妄想狂,一天,它决定在一些房间里设置隐蔽的陷阱(底部有鳄鱼)。
        但是这还不够。一星期后,他决定在他的城堡里安排尽可能多的保卫。但这不是一件容易的事。这些保卫经过训练后,在他见到人的时候,他就会立即向那个人开枪。所以国王必须小心放置保卫,如果两个保卫互相看到了对方,他们就会互相射击!而且国王显然不能把保卫放在有陷阱的房间里。
        在一个房间里的两个保卫可以互相看见对方,所以一个房间最多只能容纳一名保卫。当且仅当他们所在的房间在同一行或在同一列,且在他们之间没有墙,两个不同房间的保卫才能互相看到对方(保卫只能看见四个方向,就像国际象棋中一样)。
        你的任务是找出国王在他的城堡里最多能放几名保卫(依照上面的规则),并且找出这其中的一种放置

输入格式:
输入文件的第一行是两个整数M,N(1 ≤ M,N ≤ 200),表示城堡平面图的大小。下面 有M 行,其中的第i行,有N 个两两之间用一个空格隔开的数ai,1 , . . . , ai,N ,它们表示:
1⃝ ai,j = 0 表示块[i, j]是空的(一个没有陷阱的房间)
2⃝ ai,j =1表示块[i,j]藏有一个陷阱
3⃝ ai,j =2表示块[i,j]是墙
  注意坐标的第一个数是块的行号,第二个是块的列号。
输出格式:
输出文件的第一行应该是在城堡中能够放置的最多的保卫数K。下面K行是城堡中放置K名 保卫并且不互相攻击的一种情况。
其中第i行有两个用一个空格隔开的整数ri, ci,第i名保卫所在房间的坐标。(ri是行号,ci是 列号)
提示: 为了实现起来简单一些,我们用墙把城堡围起来。每一行被墙隔开,且包含空地的连续区域 称作行段。同样得定义列段。显然,每个段最多只能有一名保卫。
让我们构造一个二分图,把每个行段看作一个划分中的点,列段看作另一个划分中的点。若 两个段有公共的空地,则在它们之间连边。换句话说每条边代表了这个块可以站一个保卫。
如果合理地放置一些保卫,代表这些保卫的位置的边构成了一个图的匹配。每个行段和每个 列段对多只能有一个保卫,每个顶点最多能连一条边。换句话说,每一个图的匹配代表了一种合 理放置一些保卫的方法。
换句话说,要往城堡里放尽可能多的保卫,也就是要找二分图的最大匹配。有经典算法可以 在O(|V | × (|V | + |E|))时间内处理这个问题,通过反复构造增广链,交换上面匹配和未匹配的边 即可。因为|V |, |E| = O(MN),所以这个算法的时间复杂度为O(M2N2)。
样例:

输入

3 4
2 0 0 0
2 2 2 1
0 1 0 2

输出

2
1 2
3 3
登录并解答