题目描述(ID:12272)
标题: 拯救机房
标签: 搜索 广度优先搜索
详情:
H101曾经是一个由崭新的大庆土产同创电脑组成的MN列的矩阵……不过电脑上装有还原卡,而据BNJ推测,正是还原卡造成了H101部分机器蜂鸣后死机,再起不能的惨状!但这道题的题名是tsy,所以不能不提tsy与这件事的瓜葛。/*BNJ:Muhahaha…*/邪恶的tsy拿到了机房还原卡的密码后,重做了电脑……但是好景不长,大家马上发现在还原卡的保护网下,居然还有若干种autorun病毒!并且由于大家○○××,很多机器再次死机,再起不能,其他机器因病毒肆虐,生产力严重下降!于是tsy成为了全民公敌。为了给大家接下来的魔鬼训练提供良好的竞赛模拟环境,BNJ勒令tsy找到机房中“最好”的一个子矩阵作为OI队的固定用机。具体地说,机房中第i行第j列的机器有一个整数h[j]表示其“健康程度”,h[j]<=0表示该机已经彻底坏了,不可使用。要求找到一个只包含可以使用的机器的,且健康程度和最大的机器组成的子矩阵。
输入格式:
第一行仅包含两个整数M, N,为矩阵的行数与列数;
接下来有M行,每行N个整数,其中第i行的第j个整数为h[i][j]。
输出格式:
仅一行,包含一个整数,为最大的健康程度和。
限制: 对于30分的数据,满足1<=N, M<=10.
对于50分的数据,满足1<=N, M<=100.
对于100分的数据,满足1<=N, M<=900.
样例:

输入

4 4
10 0 3 8
8 5 11 0
4 6 9 2
0 5 1 7

输出

43
登录并解答