题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2870
题意：给你一个矩阵, w 可以换成a或b； x可以换成b或c； y可以换成a或c；z可以换成a, b, 或c
问只包含相同字母的最大矩阵，输出矩阵包含的字母个数
思路：（转）
因为这道题的情况比较少，即最大值只可能在字母a，b，c之间产生，所以可以枚举3中情况，之后取最大值即可。
取最大值时用动态规划的思想做，先对列统计，即高度。之后再对行统计，即宽度。再统计宽度的时候用到了并查集的思想，设置两个属性，left和right，如果后面的高度大于前面的高度，说明后面的left属性可以左移。同理，如果前面的高度小于后面的高度，说明前面的right属性可以右移。这样一直移动，直到所取到得矩形最大为止，再乘以高度，即得到该高度下的最大矩形。题目：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cstdlib> 6 #include <cmath> 7 #include <set> 8 #include <map> 9 #include <vector> 10 using namespace std; 11 12 char num[1010][1010]; 13 int heg[1010][1010], n, m, res, l[1010], r[1010]; 14 void find() 15 { 16 for(int i = 1; i <= n; i++) 17 { 18 19 for(int j = 1; j <= m; j++){ 20 r[j] = j, l[j] = j; 21 } 22 heg[i][0] = -1, heg[i][m + 1] = -1; 23 for(int j = 1; j <= m; j++){ 24 while(heg[i][j] <= heg[i][l[j] - 1]){ 25 l[j] = l[l[j] - 1]; 26 } 27 } 28 for(int j = m; j >= 1; j--){ 29 while(heg[i][j] <= heg[i][r[j] + 1]){ 30 r[j] = r[r[j] + 1]; 31 } 32 } 33 for(int j = 1; j <= m; j++){ 34 // cout << res << endl; 35 res = max(res, (r[j] - l[j] + 1) * heg[i][j]); 36 } 37 } 38 } 39 int main() 40 { 41 while(~scanf("%d %d", &n, &m)) 42 { 43 res = 0; 44 for(int i = 1; i <= n; i++) 45 scanf("%s", num[i]); 46 memset(heg, 0, sizeof(heg)); 47 for(int i = 1; i <= m; i++) 48 for(int j = 1; j <= n; j++) 49 if(num[j][i] == 'a' || num[j][i] == 'w' || num[j][i] == 'y' || num[j][i] == 'z') 50 heg[j][i] = heg[j - 1][i] + 1; 51 find(); 52 53 memset(heg, 0, sizeof(heg)); 54 for(int i = 1; i <= m; i++) 55 for(int j = 1; j <= n; j++) 56 if(num[j][i] == 'b' || num[j][i] == 'w' || num[j][i] == 'x' || num[j][i] == 'z') 57 heg[j][i] = heg[j - 1][i] + 1; 58 find(); 59 memset(heg, 0, sizeof(heg)); 60 for(int i = 1; i <= m; i++) 61 for(int j = 1; j <= n; j++) 62 if(num[j][i] == 'c' || num[j][i] == 'x' || num[j][i] == 'y' || num[j][i] == 'z') 63 heg[j][i] = heg[j - 1][i] + 1; 64 find(); 65 printf("%d ", res); 66 } 67 return 0; 68 }