Участник:ZhenyaStrelkova/ADAPATH

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/ADAPATH/

#include <iostream>
#include <vector>
 
using namespace std;
 
const int max_path = 10007;
const int max_n = 107;
const int max_a = 10;
 
int field[max_n][max_n];
int id[max_n][max_n];
int cont[max_a];
int numb;
 
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
vector<int> graph[max_path][max_a];
vector<int> match, vis;
 
 
int check(int x, int y, int n) {
    return 0 < x && x <= n && 0 < y && y <= n;
}
 
int augmenting_path(int l) {
    if (vis[l]) return 0;
    vis[l] = 1;
    for (int r: graph[l][numb]) {
        if (match[r] == -1 || augmenting_path(match[r])) {
            match[r] = l;
            return 1;
        }
    }
    return 0;
}
 
int main() {
    int T;
    cin >> T;
    for (int t = 0; t < T; t++) {
        int n;
        cin >> n;
        for (int i = 1; i < max_a; i++) {
            cont[i] = 0;
        }
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                cin >> field[i][j];
                cont[field[i][j]]++;
                id[i][j] = cont[field[i][j]];
                graph[cont[field[i][j]]][field[i][j]].clear();
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                for (int k = 0; k < 4; k++) {
                    int ni = i + dx[k];
                    int nj = j + dy[k];
                    if (check(ni, nj, n) && field[ni][nj] == field[i][j] + 1) {
                        graph[id[i][j]][field[i][j]].emplace_back(id[ni][nj]);
                    }
                }
            }
        }
        bool issue = false;
        int counter;
        for (numb = 1; numb < max_a - 1; numb++) {
            match.assign(cont[numb + 1] + 2, -1);
            counter = 0;
            for (int i = 1; i <= cont[numb] && counter < cont[numb + 1]; i++) {
                vis.assign(cont[numb] + 2, 0);
                counter += augmenting_path(i);
            }
            if (counter < cont[numb + 1]) {
                issue = true;
                break;
            }
        }
        cout << (issue ? "NO" : "YES") << "\n";
    }
    return 0;
}