6484: 轰炸任务

内存限制:256 MB 时间限制:2 S
题面:传统 评测方式:文本比较 上传者:
提交:1 通过:1

题目描述

A国要对B国的城市C进行轰炸。城市C可以看做一个n行n列的正方形, 其中空地用0表示,军事设施用1表示,民用设施用2表示,如下图所示。由于A国的轰炸机在设计时存在一定的缺陷,

只能对一整行或者一整列的目标进行轰炸,其中军用设施必须摧毁。另外出于人道主义考虑,民用设施不能被轰炸。在下图中,我们只需要轰炸第1行和第3行,以及第3列,就能够摧毁所有的军事设施。

请编程计算最少需要派出多少架轰炸机,才能摧毁城市C的所有军事设施。


1
0
0
2
0
1
1
0
1



输入格式

第一行为一个正整数n,表示城市C的规模。接下来的n行每行n个空格隔开的非负整数,表示建筑的类型,其中0表示空地,1表示军事设施,2表示民用设施。

输出格式

一行一个整数,表示最少需要派出多少架轰炸机。如果轰炸任务无法完成,则输出-1。

输入样例 复制

3
1 0 0
2 0 1
1 0 1

输出样例 复制

3

分类标签