题目描述
回到家中的猫猫把三桶鱼全部转移到了她那长方形大池子中，然后开始思考：到底要以何种方法吃鱼呢（猫猫就是这么可爱，吃鱼也要想好吃法 ^_*）。她发现，把大池子视为01矩阵（0表示对应位置无鱼，1表示对应位置有鱼）有助于决定吃鱼策略。
在代表池子的01矩阵中，有很多的正方形子矩阵，如果某个正方形子矩阵的某条对角线上都有鱼，且此正方形子矩阵的其他地方无鱼，猫猫就可以从这个正方形子矩阵“对角线的一端”下口，只一吸，就能把对角线上的那一队鲜鱼吸入口中。
猫猫是个贪婪的家伙，所以她想一口吃掉尽量多的鱼。请你帮猫猫计算一下，她一口下去，最多可以吃掉多少条鱼？
输入格式
有多组输入数据，每组数据：
第一行有两个整数n和m（n,m≥1），描述池塘规模。接下来的n行，每行有m个数字（非“0”即“1”）。每两个数字之间用空格隔开。
对于30%的数据，有n,m≤100
对于60%的数据，有n,m≤1000
对于100%的数据，有n,m≤2500
输出格式
只有一个整数——猫猫一口下去可以吃掉的鱼的数量，占一行，行末有回车。
输入输出样例
输入 #1<button class="copy-btn lfe-form-sz-middle" data-v-370e72e2="" data-v-52f2d52f="" type="button">复制</button>
4 6 0 1 0 1 0 0 0 0 1 0 1 0 1 1 0 0 0 1 0 1 1 0 1 0
输出 #1<button class="copy-btn lfe-form-sz-middle" data-v-370e72e2="" data-v-52f2d52f="" type="button">复制</button>
3
说明/提示
右上角的
1 0 0 0 1 0 0 0 1
思路
考虑这样一个问题：如果以 f[i][j][1|0] 来表示取到第 (i, j) 个位置时所能取到的最长的对角线长度，0表示左上到右下，1表示右上到左下方向，什么时候\怎样来更新 f 的值。
首先如果以 之前那道最大正方形的方法来做，只能过第一个点 1 1 0 这个数据。因为会发现这道题比最大正方形多了一个限制条件，就是在这个对角线确定的大矩形中，除了这条对角线之外不能有多余的1.
所以在从右上或左上转移时，要多加一个这个条件对状态的影响。
这个条件有什么影响？
注意到因为动态规划是由 1 ~ n 这样来推理，所以可以分析在边界 1 时的影响即可。
对于以下样例分析
1 0 0
0 1 0
0 0 1
当 i = 1, j = 1 时，显然 f = 1
当 i = 2, j = 2 时，如果 a[2][2] 的上方和右方都没有 1 ，则 f[i][j] = f[i-1][j-1] + 1 ;
如果 a[2][2] 的右方和上方有 1 ，显然 f[i][j] = 1 且应该作为一段新的开始。
由是可以推到 n 。
CODE
#include < bits/stdc++.h >
#define dbg( x ) cout << #x << " = " << x << endl
#define eps 1 e - 8
#define pi acos( - 1.0 )
using namespace std ;
typedef long long LL ;
const int inf = 0x 3f3f3f3f ;
template < class T > inline void read(T & res )
{
char c ;T flag = 1 ;
while((c = getchar()) < ' 0 ' ||c > ' 9 ' )if(c == ' - ' )flag =- 1 ;res =c - ' 0 ' ;
while((c = getchar()) >= ' 0 ' &&c <= ' 9 ' )res =res * 10 +c - ' 0 ' ;res *=flag ;
}
namespace _buff {
const size_t BUFF = 1 << 19 ;
char ibuf [BUFF ], *ib = ibuf , *ie = ibuf ;
char getc() {
if (ib == ie ) {
ib = ibuf ;
ie = ibuf + fread(ibuf , 1 , BUFF , stdin );
}
return ib == ie ? - 1 : *ib ++ ;
}
}
int qread() {
using namespace _buff ;
int ret = 0 ;
bool pos = true ;
char c = getc();
for (; (c < ' 0 ' || c > ' 9 ' ) && c != ' - ' ; c = getc()) {
assert( ~c );
}
if (c == ' - ' ) {
pos = false ;
c = getc();
}
for (; c >= ' 0 ' && c <= ' 9 ' ; c = getc()) {
ret = (ret << 3 ) + (ret << 1 ) + (c ^ 48 );
}
return pos ? ret : -ret ;
}
const int maxn = 2577 ;
int n ,m ;
int a [maxn ][maxn ];
int f [maxn ][maxn ][ 2 ];
int main()
{
//freopen("data.txt", "r", stdin);
read(n );
read(m );
for ( int i = 1 ; i <= n ; ++i ) {
for ( int j = 1 ; j <= m ; ++j ) {
read( a [i ][j ]);
}
}
int ans = 0 ;
for ( int i = 1 ; i <= n ; ++i ) {
for ( int j = 1 ; j <= m ; ++j ) {
if( a [i ][j ]) {
int up = 0 , rig = 0 ;
for ( int k = i - 1 ; k >= 1 ; --k ) {
if( a [k ][j ]) {
break;
}
++up ;
}
for ( int k = j + 1 ; k <= m ; ++k ) {
if( a [i ][k ]) {
break;
}
++rig ;
}
f [i ][j ][ 1 ] = min( f [i - 1 ][j + 1 ][ 1 ], min(up , rig )) + 1 ;
//f[i][j][1] = min(f[i - 1][j + 1][1], min(up, rig)) + 1;
}
//printf("f[%d][%d]:%d\n",i, j, f[i][j][0]);
ans = max(ans , max( f [i ][j ][ 0 ], f [i ][j ][ 1 ]));
}
for ( int j = m ; j >= 1 ; --j ) {
int up = 0 , lef = 0 ;
if( a [i ][j ]) {
for ( int k = i - 1 ; k >= 1 ; --k ) {
if( a [k ][j ]) {
break;
}
++up ;
}
for ( int k = j - 1 ; k >= 1 ; --k ) {
if( a [i ][k ]) {
break;
}
++lef ;
}
f [i ][j ][ 0 ] = min( f [i - 1 ][j - 1 ][ 0 ], min(up , lef )) + 1 ;
// if(i == 3 && j == 6) {
// printf("up:%d lef:%d f[3][6][0]:%d\n",up, lef, f[3][6][0]);
// }
// if(i == 2 && j == 5) {
// printf("up:%d lef:%d f[2][5][0]:%d\n",up, lef, f[2][5][0]);
// }
// if(i == 1 && j == 4) {
// printf("up:%d lef:%d f[1][4][0]:%d\n",up, lef, f[1][4][0]);
// }
}
ans = max(ans , max( f [i ][j ][ 0 ], f [i ][j ][ 1 ]));
}
}
cout << ans << endl ;
return 0 ;
}
京公网安备 11010502036488号