399.cpp

#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <queue>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <mutex>
#include <thread>

const int INF = (int)1e9;

// Получить текущую дату и время в формате YYYY-MM-DD.HH:mm:ss
const std::string currentDateTime() {
    time_t     now = time(0);
    struct tm  tstruct;
    char       buf[80];
    tstruct = *localtime(&now);
    strftime(buf, sizeof(buf), "%Y-%m-%d.%X", &tstruct);
    std::string s(buf);
    if (s.back() == '\n') s.pop_back();
    return s;
}

struct Solver {
    int nRows;
    int nCols;
    int map[128][128];

    // Конструктор:
    Solver(int nRows = 0, int nCols = 0, const std::vector<char>& field = {}) : nRows(nRows), nCols(nCols) {
        assert(nRows * nCols == (int)field.size());
        for (int r = 0, i = 0; r < nRows; ++r) {
            for (int c = 0; c < nCols; ++c) {
                assert(0 == field[i] || 1 == field[i]);
        map[r][c] = field[i++] * INF;
            }
        }
    }

    // Функция, определяющая, существует ли путь из стартовой точки в конечную
    bool isset_path() {
        std::queue<std::pair<int, int>> q;
        q.push({1, 1});
        map[1][1] = 1;
        while (!q.empty()) {
            auto curr = q.front(); q.pop();
            int r = curr.first, c = curr.second;
            if (map[r+1][c] == 0) {
                map[r+1][c] = 1;
                q.push({r+1, c});
            }
            if (map[r-1][c] == 0) {
                map[r-1][c] = 1;
                q.push({r-1, c});
            }
            if (map[r][c+1] == 0) {
                map[r][c+1] = 1;
                q.push({r, c+1});
            }
            if (map[r][c-1] == 0) {
                map[r][c-1] = 1;
                q.push({r, c-1});
            }
        }
        bool result = map[nRows-2][nCols-2];
        backup();
        return result;
    }

    // Откатить изменения на поле к первоначальному виду:
    void backup() {
        for (int r = 0; r < nRows; ++r) {
            for (int c = 0; c < nCols; ++c) {
                map[r][c] = (map[r][c] == INF) ? INF : 0;
            }
        }
    }

    // Промоделировать действия жука для получения ответа:
    int solve() {
        if (!isset_path()) {
            return -1;
        }
        int r = 1, c = 1, dir = 0, answ = 0;
        const int dr[4] = { 1, 0, -1,  0};
        const int dc[4] = { 0, 1,  0, -1};
        do {
            map[r][c]++;
            int min = std::min({
                map[r-1][c], map[r+1][c], map[r][c+1], map[r][c-1]
            });

            if (map[r+dr[dir]][c+dc[dir]] != min) {
                for (int next = 0; next < 4; ++next) {
                    if (map[r+dr[next]][c+dc[next]] == min) {
                        dir = next;
                        break;
                    }
                }
            }
            ++answ;
            r += dr[dir];
            c += dc[dir];
        } while (!(r == nRows-2 && c == nCols-2));
        backup();
        return answ;
    }
};

struct Mask {
    int row, col;
    std::vector<std::vector<char>> data;

    static Mask gen(int row, int col, int side, int p0, int p1) {
        std::vector<std::vector<char>> data(side, std::vector<char>(side));
        for (int i = 0; i < side; ++i)
            for (int j = 0; j < side; ++j)
                data[i][j] = (rand() % (p0 + p1) >= p0);
        return Mask{row, col, std::move(data)};
    }
};

/*
bool operator<(const Square& a, const Square& b) {
    return a.row < b.row || (a.row == b.row && (a.col < b.col || (a.col == b.col && a.side < b.side)));
} */

// Генерация случайных масок
std::vector<Mask> gen_squares(int nRows, int nCols, int min_count, int max_count, int max_side, int p0, int p1) {
    std::vector<Mask> answer;
    const int count = rand() % (max_count - min_count + 1) + min_count;
    assert(min_count <= count && count <= max_count);
    while ((int)answer.size() < count) {
        const int side = rand() % max_side + 1;
        const int row = rand() % (nRows-side-1)+1;
        const int col = rand() % (nCols-side-1)+1;
        assert(1 <= side && side <= max_side);
        assert(1 <= row && row <= nRows-2);
        assert(1 <= col && col <= nCols-2);
        auto mask = Mask::gen(row, col, side, p0, p1);
        // Если стартовая клетка или конечная задета, то фигура не подходит:
        if ((row == 1 && col == 1 && mask.data[0][0]) || (row + side - 1 == nRows-2 && col + side - 1 == nCols-2 && mask.data.back().back())) {
            continue;
        }
        answer.push_back(mask);
    }
    return answer;
}

// Применение инверсий внутри квадратов к полю:
std::vector<char> modify(int nRows, int nCols, std::vector<char> field, const std::vector<Mask>& squares) {
    assert(nRows*nCols == (int)field.size());
    for (const auto& s : squares) {
        for (int dr = 0; dr < (int)s.data.size(); ++dr) {
            for (int dc = 0; dc < (int)s.data[0].size(); ++dc) {
                int row = s.row + dr;
                int col = s.col + dc;
                if (s.data[dr][dc]) {
                    auto& it = field[row * nCols + col];
                    it = 1 - it;
                }
            }
        }
    }
    return field;
}

// Запись поля в файл:
void print_field(const int nRows, const int nCols, const std::vector<char>& field, const std::string& filename) {
    auto file = fopen(filename.c_str(), "wt");
    assert(file != 0);
    fprintf(file, "%d %d\n", nRows, nCols);
    for (int r = 0; r < nRows; ++r) {
        for (int c = 0; c < nCols; ++c) {
            fprintf(file, "%c", field[r*nCols+c] == 1 ? '@' : ' ');
        }
        fprintf(file, "\n");
    }
    fclose(file);
}

// Чтение поля из файла:
std::vector<char> read_field(int &nRows, int& nCols, const std::string& filename) {
    std::vector<char> field;
    auto file = fopen(filename.c_str(), "rt");
    assert(file != 0);
    fscanf(file, "%d %d", &nRows, &nCols); fscanf(file, "\n");
    for (int r = 0; r < nRows; ++r) {
        char buf[101];
    fscanf(file, "%[^\n]s", buf); fscanf(file, "\n");
        for (int c = 0; c < nCols; ++c) {
            field.push_back(buf[c] == '@');
        }
    }
    fclose(file);
    return field;
}

// Многопоточный алгоритм поиска:
void search(
    const int nRows,         // кол-во строк
    const int nCols,         // кол-во столбцов
    std::vector<char> field, // начальное приближение поля
    int nThreads,            // кол-во потоков
    const int min_count,     // минимальное кол-во квадратов инверсий
    const int max_count,     // максимальное кол-во квадратов инверсий
    const int max_side,      // максимальная сторона квадрата инверсий
    const int p0,            // вероятность появления нуля в маске p0 / (p0+p1)
    const int p1             // вероятность появления единицы в маске p1 / (p0+p1)
) {
    assert(nRows * nCols == (int)field.size());
    assert(nThreads >= 1);

    srand(time(0));

    nThreads = std::min(nThreads, (int)std::thread::hardware_concurrency());

    std::mutex mtx;

    int curr = Solver(nRows, nCols, field).solve();

    std::vector<std::thread> threads;
    std::vector<uint64_t> Time(1+nThreads, clock());

    for (int i = 1; i <= nThreads; ++i) {
        threads.push_back(std::thread([&, id = i]{
            while (1) {
                mtx.lock();
                int answ = curr;
                auto fld = field;
                mtx.unlock();

                fld = modify(nRows, nCols, fld, gen_squares(nRows, nCols, min_count, max_count, max_side, p0, p1));

                int temp = Solver(nRows, nCols, fld).solve();
                auto dt = clock() - Time[id];
                if (dt >= 60 * CLOCKS_PER_SEC) {
                    std::cout << currentDateTime() << ": thread #" << id << " working, don't worry, curr = " << std::setw(9) << curr << std::endl;
                    Time[id] += dt;
                }
        if (temp >= answ) {
                    mtx.lock();
                    if (temp >= curr) {
                        if (temp > curr) {
                            std::cout << currentDateTime() << ": thread #" << id << " got result = " << std::setw(9) << temp << std::endl;
                            char buf[101]; sprintf(buf, "test%09d.txt", temp);
                            print_field(nRows, nCols, fld, buf);
                        }
                        field = fld;
                        curr = temp;
                    }
                    mtx.unlock();
                }
            }
            return;
        }));
    }

    for (auto & t : threads) t.join();
}

// Генерация случайного поля размера nRows x nCols
// гарантируется, что на сгенерированном поле будет проход:
// (1, 1) --> (nRows-2, nCols-2)
std::vector<char> rand_field(int nRows, int nCols) {
    srand(time(0));

    std::vector<char> field(nRows*nCols);

    for (int r = 0; r < nRows; ++r)
        field[r*nCols] = field[r*nCols+nCols-1] = 1;

    for (int c = 0; c < nCols; ++c)
        field[c] = field[(nRows-1)*nCols+c] = 1;

    do {
        for (int r = 1; r <= nRows-2; ++r) {
            for (int c = 1; c <= nCols-2; ++c) {
                if ((r == 1 && c == 1) || (r == nRows-2 && c == nCols-2)) {
                    field[r*nCols+c] = 0;
                } else {
                    field[r*nCols+c] = rand() % 2;
                }
            }
        }
    } while (Solver(nRows, nCols, field).solve() == -1);
    return field;
}

int main(int argc, char* argv[]) {
    assert((argc-1) % 2 == 0);

    std::string filename = "input.txt";
    int nThreads = std::thread::hardware_concurrency();
    int minCount = 1;
    int maxCount = 6;
    int maxSide  = 3;
    int pZeros   = 1;
    int pOnes    = 3;

    std::cout << "Params from command line:" << std::endl;
    for (int i = 1; i < argc; i += 2) {
        std::cout << "\t" << argv[i] << " = " << argv[i+1] << std::endl;
    std::string command(argv[i]);
        if (command == "nThreads") nThreads = atoi(argv[i+1]);
        if (command == "minCount") minCount = atoi(argv[i+1]);
        if (command == "maxCount") maxCount = atoi(argv[i+1]);
        if (command == "maxSide") maxSide = atoi(argv[i+1]);
        if (command == "pZeros") pZeros = atoi(argv[i+1]);
        if (command == "pOnes") pOnes = atoi(argv[i+1]);
        if (command == "filename") filename = argv[i+1];
    }
    std::cout << std::endl << "Params:\n";
    std::cout << "\tfilename = " << filename << std::endl;
    std::cout << "\tnThreads = " << nThreads << std::endl;
    std::cout << "\tminCount = " << minCount << std::endl;
    std::cout << "\tmaxCount = " << maxCount << std::endl;
    std::cout << "\tmaxSide  = " << maxSide  << std::endl;
    std::cout << "\tpZeros   = " << pZeros   << std::endl;
    std::cout << "\tpOnes    = " << pOnes    << std::endl;
    int nRows = 21, nCols = 31;
    //auto field = rand_field(nRows, nCols);
    auto field = read_field(nRows, nCols, filename);
    //std::cout << "rand field success!" << std::endl;
    search(nRows, nCols, field, nThreads, minCount, maxCount, maxSide, pZeros, pOnes);
    return 0;
}