| 标题: |
拯救机房 |
| 标签: |
搜索
广度优先搜索
|
| 详情: |
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
|
|
|
|
