399.cpp

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <ctime>

const int INF = (int)1e9;

// Get current date/time, format is YYYY-MM-DD.HH:mm:ss
const std::string currentDateTime() {
    time_t     now = time(0);
    struct tm  tstruct;
    char       buf[80];
    tstruct = *localtime(&now);
    // Visit http://en.cppreference.com/w/cpp/chrono/c/strftime
    // for more information about date/time format
    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];
    int lastAnswer;

    Solver(int nRows = 0, int nCols = 0) : nRows(nRows), nCols(nCols) {
        for (int r = 0; r < nRows; ++r) {
            map[r][0] = map[r][nCols-1] = INF;
        }

        for (int c = 0; c < nCols; ++c) {
            map[0][c] = map[nRows-1][c] = INF;
        }

        for (int r = 1; r <= nRows-2; ++r) {
            for (int c = 1; c <= nCols-2; ++c) {
                map[r][c] = 0;
            }
        }
    }

    bool isset_path() {
        std::queue<std::pair<int, int>> q;
        std::vector<std::pair<int, int>> s;
        q.push({1, 1});
        map[1][1] = 1;
        while (!q.empty()) {
            auto curr = q.front(); q.pop(); s.push_back(curr);
            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 count() {
        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 lastAnswer = answ;
    }

    bool next_generation() {
        int max = count();
        bool success = false;
        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))) {
                    // Попробуем поменять:
                    map[r][c] = INF - map[r][c];
                    // Попробуем решить:
                    int temp = count();
                    // Проверим, не обновился ли текущий максимум:
                    if (max < temp) {
                        max = temp;
                        success = true;
                    } else { // Если не помогло, то вернем обратно:
                        map[r][c] = INF - map[r][c];
                    }
                }
            }
        }
        return success;
    }

    void print(std::string filename) {
        auto file = fopen(filename.c_str(), "wt");
        fprintf(file, "%d %d\n", nRows, nCols);
        for (int r = 0; r < nRows; ++r) {
            for (int c = 0; c < nCols; ++c) {
                fprintf(file, "%c", map[r][c] == INF ? '@' : ' ');
            }
            fprintf(file, "\n");
        }
        fprintf(file, "answ = %d", answer);
        flose(file);
    }

    void learning() {
        uint64_t t = clock(); // 1000
        int i = 0;
        while (next_generation()) {
            auto dt = clock() - t;
            if (dt >= CLOCKS_PER_SEC) {
                char buf[101];
                sprintf(buf, "test%04d.txt", i++);
                print(buf);
                std::cout << currentDateTime() << ": " << lastAnswer << endl;
                t += dt;
            }
        }
    }

    static Solver read() {
        int nRows, nCols;
        scanf("%d %d\n", &nRows, &nCols);

        Solver solver(nRows, nCols);

        for (int r = 0; r < nRows; ++r) {
            char buf[101];
            scanf("%[^\n]s", buf); scanf("\n");
            for (int c = 0; c < nCols; ++c) {
                solver.map[r][c] = (buf[c] == '@') ? INF : 0;
            }
        }
        return solver;
    }
};

int main() {
    Solver solver(21, 31);
    solver.learning();
    return 0;
}