标题: |
拯救机房 |
标签: |
搜索
广度优先搜索
|
详情: |
H101曾经是一个由崭新的大庆土产同创电脑组成的M行N列的矩阵……不过电脑上装有还原卡,而据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
|
|
|