399.cpp

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

const int INF = (int)1e9;

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

    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];
        while (!s.empty()) {
            int r = s.back().first, c = s.back().second;
            map[r][c] = 0;
            s.pop_back();
        }
        return result;
    }

    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));
        return answ;
    }

    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("input.txt", "rt", stdin);
    auto solver = Solver::read();
    printf("%d", solver.count());
    return 0;
}