Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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_v = count(), max_r = -1, max_c = -1;
- //printf("max = %d\n", max_v);
- 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();
- //printf("temp = %d\n", temp);
- // Âåðíåì:
- map[r][c] = INF - map[r][c];
- // Ïðîâåðèì, íå îáíîâèëñÿ ëè òåêóùèé ìàêñèìóì:
- if (max_v <= temp) {
- max_v = temp;
- max_r = r;
- max_c = c;
- success = true;
- }
- }
- }
- }
- if (success) {
- map[max_r][max_c] = INF - map[max_r][max_c];
- lastAnswer = max_v;
- }
- 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", lastAnswer);
- fclose(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);
- printf("%s: %9d\n", currentDateTime().c_str(), lastAnswer);
- fflush(stdout);
- t += dt;
- }
- }
- char buf[101];
- sprintf(buf, "test%04d.txt", i++);
- print(buf);
- printf("%s: %9d\n", currentDateTime().c_str(), lastAnswer);
- fflush(stdout);
- }
- 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() {
- //freopen("output.txt", "wt", stdout);
- Solver solver(21, 31);
- solver.learning();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement