切换到宽版
  • 5377阅读
  • 2回复

0-1矩阵问题求解 [复制链接]

上一主题 下一主题
离线tzwangzy
 
只看楼主 正序阅读 0 发表于: 2007-08-24
0-1矩阵
(matrix.pas)
[问题描述]
给定一个01矩阵(即矩阵中的元素仅为0或1),每次操作可以选择某一行或某一列,将其
中的1全部删除。
问最少必须进行多少次操作,才可以将01矩阵中所有的1全部删除。
[输入输出]
输入文件名为matrix.in。
输入的第一行是两个用空格隔开的正整数m,n,其中1<=m,n<=100。
接下来的m行是一个m*n的01矩阵。
[输出]
输出文件名为matrix.out。
输出文件只包含一个正整数,即删除所有的1所需的最少操作次数。
【样例】
Matrix.in
4  4
0 1 0 1
1 0 1 0
0 1 0 0
0 1 0 1
Matrix.out
3
离线orangeclk
只看该作者 2 发表于: 2007-08-24
广搜。
注意每一行每一列最多只枚举一次就够了,这个优化必须加,否则会超时的。
RP降至零点,NOIP2007完美彻底挂掉。。。
离线tzwangzy
只看该作者 1 发表于: 2007-08-24
很难呀!!!!!!!!!!!!!!!!!
快速回复
限100 字节
 
上一个 下一个