问题描述
小R拿到了一个 n 行 m 列的小写字母矩阵，她想知道有多少个子矩阵满足以下条件：每个字母在这个子矩阵中最多出现一次。
测试样例
样例1：
输入：
n = 2 ,m = 3 ,s = ["aad", "abc"]
输出：13
样例2：
输入：
n = 3 ,m = 3 ,s = ["abc", "def", "ghi"]
输出：36
样例3：
输入：
n = 4 ,m = 4 ,s = ["abcd", "efgh", "ijkl", "mnop"]
输出：100
题解：
直接大遍历，纯暴力。本来有想过使用动态规划，但是似乎不那么好找转台转移，就放弃了。
代码：
#include<iostream>
#include<string>
#include<cstdio>
#include<unordered_map>
#include<vector>
#include<set>
using namespace std;int found(int x,int y,int n,int m,vector<string>s){int i,j,sum=0,h,k,t=0;set<char> st;for(i=0;i<=n-x;i++){for(j=0;j<=m-y;j++){st.clear();t=0;for(k=i;k<i+x;k++){for(h=j;h<j+y;h++){if(st.find(s[k][h])!=st.end()){t=1;}else{st.insert(s[k][h]);}}}if(!t){sum++;}}}return sum;
}int solution(int n, int m, std::vector<std::string> s) {// write code hereint i,j,sum=0;for(i=1;i<=n;i++){for(j=1;j<=m;j++){//cout << i << " " << j << "\n";sum+=found(i,j,n,m,s);}}//cout << sum << "\n";return sum;
}int main() {std::cout << (solution(2, 3, {"aad", "abc"}) == 13) << std::endl;std::cout << (solution(3, 3, {"abc", "def", "ghi"}) == 36) << std::endl;std::cout << (solution(4, 4, {"abcd", "efgh", "ijkl", "mnop"}) == 100) << std::endl;
}