这题看了别人讨论才做出来。
暴力法：枚举所有的矩形，然后统计各个矩形中的字符数。这样时间复杂度O(n^12)必然超时。
可以反过来考虑问题，对于矩形中的每一个单元，会有多少个矩形包含它。
这样思考，问题就很简单了：
一个矩形可以由它的左上角和右下角唯一决定。
而若某单元(x,y)包括在某矩形中，那么，这个矩形的左上角(x',y')必然为(0<=x'<=x),(0<=y'<=y).
右上角(x'',y'')必然为(x<=x''<c),(y<=y''<r).c为总列数,r为总行数。
这样的矩形显然有(x+1)(y+1)(c-x)(c-y)个。(坐标均为0-based)
代码如下：
class SubrectanglesOfTable
{
public:
vector<long long> getQuantity(vector <string> t)
{
vector<long long> res(26);
for(int i=0;i<t.size();++i)
t[i]+=t[i];
int tmp = t.size();
for(int i=0;i<tmp;++i)
t.push_back(t[i]);
int r = t.size();
int c = t[0].size();
for(int i=0;i<r;++i)
for(int j=0;j<c;++j){
res[ t[i][j]-'A']+=(i+1)*(j+1)*(r-i)*(c-j);
}
return res;
}
｝
其实不需要生成字符串的四个拷贝。