Cod sursa(job #3242401)

Utilizator Commander_XDunel Stefan-Octavian Commander_X Data 11 septembrie 2024 21:00:25
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
//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;
}