9 контест Надару

// 1 task
#include <iostream>
#include <vector>

using namespace std;


int n, m, a, b;
int free_cell_counter = 0;
vector<bool> used;

vector<vector<int>> graph;
vector<int> match;

bool dfs(int v) {
    if (used[v])
        return false;
    used[v] = true;
    for (int i = 0; i < graph[v].size(); i++) {
        int to = graph[v][i];
        if (match[to] == -1 || dfs(match[to])) {
            match[to] = v;
            return true;
        }
    }
    return false;
}

void handle_simbols(vector<string> &s, int i, int j){
    if (i && (s[i - 1][j] == '*'))
        graph[i * m + j].push_back((i - 1) * m + j);

    if ((i < n - 1) && (s[i + 1][j] == '*'))
        graph[i * m + j].push_back((i + 1) * m + j);

    if (j && (s[i][j - 1] == '*'))
        graph[i * m + j].push_back(i * m + j - 1);

    if ((j < m - 1) && (s[i][j + 1] == '*'))
        graph[i * m + j].push_back(i * m + j + 1);
}

vector<string> s;
void init() {

    s.resize(n);
    for (int i = 0; i < s.size(); i++) {
        cin >> s[i];
    }

    int nm = n*m;

    match.assign(nm, -1);
    graph = vector<vector<int>>(nm);
    used.resize(nm);
    match.resize(nm);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (s[i][j] == '.')
                continue;
            free_cell_counter++;
            if ((i + j) % 2)
                continue;


            handle_simbols(s, i, j);
        }
    }
}





int main() {
    cin >> n >> m >> a >> b;

    init();

    if (2 * b <= a) {
        cout << free_cell_counter * b;
        return 0;
    }


    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if ((i + j) % 2 == 1)
                continue;
            used.assign(n * m, false);
            dfs(i * m + j);
        }
    }
    int answer = 0;
    for (int i = 0; i < n * m; i++) {
        if (match[i] != -1)
            answer++;
    }

    cout << answer * a + (free_cell_counter - 2 * answer) * b;

    return 0;
}

// 2 task
#include <iostream>
#include <vector>

using namespace std;


int n, m;
int free_cell_counter = 0;
vector<bool> used;

vector<vector<int>> graph;
vector<int> match;
string sister_name;

bool dfs(int v) {
    if (used[v])
        return false;
    used[v] = true;
    for (int i = 0; i < graph[v].size(); i++) {
        int to = graph[v][i];
        if (match[to] == -1 || dfs(match[to])) {
            match[to] = v;
            return true;
        }
    }
    return false;
}

void handle_simbols(vector<string> &s, int i, int j) {
    if (i && (s[i - 1][j] == '*'))
        graph[i * m + j].push_back((i - 1) * m + j);

    if ((i < n - 1) && (s[i + 1][j] == '*'))
        graph[i * m + j].push_back((i + 1) * m + j);

    if (j && (s[i][j - 1] == '*'))
        graph[i * m + j].push_back(i * m + j - 1);

    if ((j < m - 1) && (s[i][j + 1] == '*'))
        graph[i * m + j].push_back(i * m + j + 1);
}

vector<string> s;

void init() {


    match.assign(n, -1);
    graph = vector<vector<int>>(n);
    used.resize(n);
    match.resize(n);
    for (int i = 0; i < sister_name.size(); i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < 6; k++) {
                if (sister_name[i] == s[j][k]) {
                    graph[j].push_back(i);
                }
            }
        }
    }
}


int main() {
    cin >> n >> sister_name;
    if (sister_name.size() > n) {
        cout << "NO";
        return 0;
    }
    s.resize(n);
    for (int i = 0; i < s.size(); i++) {
        cin >> s[i];
    }

    init();


    for (int i = 0; i < n; i++) {
        used.assign(n, false);
        dfs(i);

    }
    for (int i = 0; i < n; i++) {
        if (match[i] == -1) {
            cout << "NO";
            return 0;
        }
    }

    cout << "YES" << endl;
    for (int i = 0; i < match.size(); i++) {
        cout << match[i] + 1 << ' ';
    }

    return 0;
}