Pagini recente » Cod sursa (job #682071) | Cod sursa (job #623197) | Cod sursa (job #2558947) | Cod sursa (job #1973135) | Cod sursa (job #3242401)
//https://www.infoarena.ro/problema/matrix
#include <fstream>
#include <vector>
std::ifstream fin("matrix.in");
std::ofstream fout("matrix.out");
using namespace std;
vector<vector<bool>> dp;
vector<vector<int>> mat;
vector<vector<char>> M;
vector<int> F;
int main()
{
int n, m, sol = 0;
char c;
fin >> n >> m;
M.resize(n + 1, vector<char>(n + 1));
mat.resize(n + 1, vector<int>(n + 1, 0));
dp.resize(n + 1, vector<bool>(n + 1, true));
F.resize(26, 0);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
fin >> M[i][j];
for (int i = 0; i < m * m; ++i)
{
fin >> c;
F[c - 'a']++;
}
for (char c = 'a'; c <= 'z'; ++c)
{
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
mat[i][j] = (M[i][j] == c) + mat[i][j - 1] + mat[i - 1][j] - mat[i - 1][j - 1];
for (int i = m; i <= n; ++i)
for (int j = m; j <= n; ++j)
if (mat[i][j] - mat[i - m][j] - mat[i][j - m] + mat[i - m][j - m] != F[c - 'a'])
dp[i][j] = false;
}
for (int i = m; i <= n; ++i)
for (int j = m; j <= n; ++j)
sol += dp[i][j];
fout << sol;
}