学步园

       例如从：  0 1 0 1 0     中找出最大0，1间隔矩阵，结果应用从第一行第一列到第三行第四列的矩阵 0 1 0 1  ,算法实现参照从0-1矩阵中找全

                         1 0 1 0 0                                                                                                                                           1 0 1 0

                         0 1 0 1 0                                                                                                                                           0 1 0 1

0矩阵的算法：一行一行的找，记录下当前元素在纵列中的深度，若与上一行同列元素不同，高度加一，若相同，赋为1；遍历完整行后，依次找出当前高度的最左端列号和最右端列号，然后计算出包含的元素个数。

代码如下：

#include <iostream><br /> #include <stdio.h><br /> #include <string.h><br /> using namespace std;<br /> #define MAXN 2010<br /> int h[MAXN],r[MAXN],l[MAXN];<br /> int map[MAXN][MAXN];<br /> int n,m;<br /> void all_0_matrix()<br /> {<br /> int i,j,max = 0, max_i, max_h, max_l, max_r;<br /> memset(h,0,sizeof(h));<br /> for(i = 0; i < n; i++)<br /> {<br /> for(j = 0 ; j < m; j++)<br /> {<br /> if(i > 0 && map[i][j] != map[i-1][j])<br /> h[j] ++;<br /> else h[j] = 1;<br /> }<br /> for(j = 0; j < m; j ++)<br /> {<br /> l[j] = j;<br /> while(l[j] > 0 && h[j] <= h[l[j] - 1] && map[i][l[j]] != map[i][l[j] - 1])<br /> l[j] = l[l[j] - 1];<br /> }<br /> for(j = m-1; j >= 0; j --)<br /> {<br /> r[j] = j;<br /> while(r[j] < m-1 && h[j] <=h[r[j] + 1] && map[i][r[j]] != map[i][r[j] + 1])<br /> r[j] = r[r[j] + 1];<br /> }<br /> for(j = 0; j < m; j ++)<br /> {<br /> if((r[j] - l[j] + 1) * h[j] > max)<br /> {<br /> max = (r[j] - l[j] + 1) * h[j];<br /> max_i = i;<br /> max_h = h[j];<br /> max_l = l[j];<br /> max_r = r[j];<br /> }<br /> }<br /> }<br /> cout << "Max matrix is start at ( " << max_i - max_h + 1 << ", " << max_l << "), "<br /> << " end at ( " << max_i << ", " << max_r << ")." << endl;<br /> for (i = max_i - max_h + 1; i <= max_i; i++)<br /> {<br /> for (j = max_l; j <= max_r; j++)<br /> cout << map[i][j] << "/t";<br /> cout << endl;<br /> }<br /> cout << endl;<br /> }<br /> int main()<br /> {<br /> int i , j;<br /> cin >> n >> m;<br /> for(i = 0; i < n; i++)<br /> {<br /> for(j = 0; j < m; j++)<br /> {<br /> cin >> map[i][j];<br /> }<br /> }<br /> cout << endl;<br /> all_0_matrix();<br /> }<br />  

运行结果如下：

3 5

0 1 0 1 0

1 0 1 0 0

0 1 0 1 0

Max matrix is start at ( 0, 0),  end at ( 2, 3).

0 1 0 1

1 0 1 0

0 1 0 1