Cod sursa(job #2767856)

Utilizator DragosC1Dragos DragosC1 Data 8 august 2021 11:55:34
Problema Matrix Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <fstream>
#include <iostream>
using namespace std;

int n, m;
char a[1001][1001];
int fr[26];
int cur[26];

void read() {
    int i, j;
    char ch;
    ifstream f("matrix.in");
    f >> n >> m;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            f >> a[i][j];
    for (i = 1; i <= m; i++)
        for (j = 1; j <= m; j++) {
            f >> ch;
            fr[ch - 'a']++;
        }
    f.close();
}

int cnt;
int lin, col;

void shift_right() {
    int i;
    for (i = 1; i <= m; i++) {
        cur[a[lin + i - 1][col] - 'a']--;
        cur[a[lin + i - 1][col + m] - 'a']++;
    }
    col++;
    bool ok = 1;
    for (i = 0; i <= 25; i++)
        if (cur[i] != fr[i])
            ok = 0;
    if (ok)
        cnt++;
}

void shift_left() {
    int i;
    for (i = 1; i <= m; i++) {
        cur[a[lin + i - 1][col] - 'a']--;
        cur[a[lin + i - 1][col - m] - 'a']++;
    }
    col--;
    bool ok = 1;
    for (i = 0; i <= 25; i++)
        if (cur[i] != fr[i])
            ok = 0;
    if (ok)
        cnt++;
}

void shift_down() {
    int j;
    if (lin % 2 == 1) {
        for (j = n; j >= m - n + 1; j--) {
            cur[a[lin][j] - 'a']--;
            cur[a[lin + m][j] - 'a']++;
        }
        col = n;
    }
    else {
        for (j = 1; j <= m; j++) {
            cur[a[lin][j] - 'a']--;
            cur[a[lin + m][j] - 'a']++;
        }
        col = 1;
    }
    lin++;
    bool ok = 1;
    for (int i = 0; i <= 25; i++)
        if (cur[i] != fr[i])
            ok = 0;
    if (ok)
        cnt++;
}

void solve() {
    int i, j;
    bool ok;
    for (i = 1; i <= m; i++)
        for (j = 1; j <= m; j++)
            cur[a[i][j] - 'a']++;
    ok = 1;
    for (i = 0; i <= 25; i++)
        if (cur[i] != fr[i])
            ok = 0;
    if (ok)
        cnt++;
    lin = col = 1;
    for (i = 1; i <= n - m + 1; i++) {
        for (j = 2; j <= n - m + 1; j++)
            if (i % 2 == 1)
                shift_right();
            else shift_left();
        shift_down();
    }
}

void output() {
    ofstream g("matrix.out");
    g << cnt;
    g.close();
}

int main() {
    read();
    solve();
    output();
    return 0;
}