2326: A.基站(net)
Memory Limit：128 MB
Time Limit：1.000 S
：
Creator：
Submit：19
Solved：7
Description
一个 n × m 的矩形，单元格 (x, y) 表示其位于第 x 行第 y 列。科学家发明了一种新型网络系统，这种新型网络系统中可以建立多个子网，每个子网需要建立一个 1 号基站 (x1, y1 ) 和 2 号基站 (x2, y2 ) ，该子网可以覆盖以 (x1, y1 ) 和 (x2, y2 ) 为顶点的矩形区域（矩形区域的四条边必须平行于行和列）。
1 号基站只能在标记为 1 的单元格中建立，2 号基站只能在矩形的四个顶点单元格（标记为 2 ）中建立。
不同的子网覆盖区域之间可以相互重叠。
同一个单元格可以建立多个基站。
问最少需要建立多少个子网能将矩形中所有的单元格覆盖。
1 号基站只能在标记为 1 的单元格中建立，2 号基站只能在矩形的四个顶点单元格（标记为 2 ）中建立。
不同的子网覆盖区域之间可以相互重叠。
同一个单元格可以建立多个基站。
问最少需要建立多少个子网能将矩形中所有的单元格覆盖。
Input
第 1 行 1 个整数 T ，表示有 T 组测试数据，每一组数据输入如下：
第 1 行 2 个整数 n, m ，表示矩形的行数和列数。
接下来 n 行描述了矩形中单元格的属性。
第 i 行包含 m 个整数 ai,1 , ai,2 , ..., ai,m ，用空格分隔。如果 ai,j 为 0 ，表示单元格 (i, j) 不能建立任何基站。如果 ai,j 为 1 ，表示单元格 (i, j) 可以建立 1 号基站。如果 ai,j 为 2 ，表示单元格 (i, j) 可以建立 2 号基站。
Output
输出 T 行，每行 1 个整数，表示如果能将所有单元格覆盖，需要建立的最少子网数量。
Sample Input
1
4 4
2 0 0 2
0 1 0 0
0 0 1 0
2 0 0 2Sample Output
4HINT
样例1解释
样例 1 中，最少需要建立 4 个子网，其中一种情况如下：建立子网 1 ，选择 1 号方格 (2, 2) 和 2 号方格 (1, 1) ；
建立子网 2 ，选择 1 号方格 (3, 3) 和 2 号方格 (1, 4) ；
建立子网 3 ，选择 1 号方格 (3, 3) 和 2 号方格 (4, 1) ；
建立子网 4 ，选择 1 号方格 (3, 3) 和 2 号方格 (4, 4) 。 
样例2解释
样例 2 中，最少需要建立 2 个子网，其中一种情况如下：
建立子网 1 ，选择 1 号方格 (2, 1) 和 2 号方格 (1, 3) ；
建立子网 2 ，选择 1 号方格 (3, 1) 和 2 号方格 (4, 3) ； 
数据范围
对于 30% 的数据，3 ≤ n, m ≤ 50 ；
对于 100% 的数据，1 ≤ T ≤ 10，3 ≤ n, m ≤ 100 。