*[topcoder]TheMatrix

http://community.topcoder.com/stat?c=problem_statement&pm=13035

矩阵棋盘的题,比较典型。可以定两条column夹住,然后上下扫,上下扫过程中有一点DP的东西,这样负责度是o(n^3)

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std; class TheMatrix {
public:
int MaxArea(vector <string> board) {
int N = board.size();
int M = board[0].size();
int maxArea = 1;
// fix i, j column
for (int i = 0; i < M; i++) {
vector<char> row(N);
for (int j = i; j < M; j++) {
for (int k = 0; k < N; k++) {
if (j == i) {
row[k] = board[k][j];
} else {
if (board[k][j] == board[k][j - 1])
row[k] = 'X';
}
}
int maxLen = 0;
int len = 0;
for (int k = 0; k < N; k++) {
if (row[k] == 'X') {
len = 0;
} else if (k == 0) {
len = 1;
} else if (k > 0 && row[k] != row[k - 1]) {
len++;
} else {
len = 1;
}
maxLen = max(len, maxLen);
}
int area = maxLen * (j - i + 1);
maxArea = max(area, maxArea);
}
}
return maxArea;
}
};

  

上一篇:PC端的鼠标拖拽滑动


下一篇:使用Trinity拼接以及分析差异表达一个小例子