soricel3

#include <queue>
#include <fstream>

#define DMAX 80

std::ifstream fin("soricel3.in");
std::ofstream fout("soricel3.out");

const int dL[] = {-1, 0, 1,  0};
const int dC[] = { 0, 1, 0, -1};

struct Pos {
    int lin;
    int col;
};

int m, n;
int mat[DMAX][DMAX];

int nr;
int dp[DMAX][DMAX];

class cmp {
    bool reverse;
public:
    cmp(const bool& revParam = false) {
        reverse = revParam;
    }

    bool operator() (const Pos& x, const Pos& y) const {
        if (reverse)
            return mat[x.lin][x.col] < mat[y.lin][y.col];
        return mat[x.lin][x.col] > mat[y.lin][y.col];
    }
};

std::queue<Pos> q;
std::priority_queue<Pos, std::vector<Pos>, cmp> d;

inline int min(int x, int y) {
    return x < y ? x : y;
}

inline bool isInMat(Pos pos) {
    return 1 <= pos.lin && pos.lin <= m &&
           1 <= pos.col && pos.col <= n;
}

void solve(int lin, int col, int len) {
    if (lin == 1 && col == 1) {
        fout << ' ' << len << "\n1 1\n";
        return;
    }

    int newLin, newCol;
    for (int i = 0; i < 4; i++) {
        newLin = lin + dL[i];
        newCol = col + dC[i];

        if (isInMat({newLin, newCol}) && dp[newLin][newCol] == dp[lin][col] - mat[lin][col]) {
            solve(newLin, newCol, len + 1);
            fout << lin << ' ' << col << '\n';
            return;
        }
    }
}

int main() {
    int x, y;

    fin >> m >> n >> nr;
    for (int i = 0; i < nr; i++) {
        fin >> x >> y;
        q.push({x, y});
        mat[x][y] = m + n;
    }

    Pos pos, v;
    while (!q.empty()) {
        pos = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            v.lin = pos.lin + dL[i];
            v.col = pos.col + dC[i];

            if (isInMat(v) && !mat[v.lin][v.col]) {
                mat[v.lin][v.col] = mat[pos.lin][pos.col] - 1;
                q.push(v);
            }
        }
    }

    d.push({1, 1});
    dp[1][1] = mat[1][1];

    while (!d.empty()) {
        pos = d.top();
        d.pop();

        for (int i = 0; i < 4; i++) {
            v.lin = pos.lin + dL[i];
            v.col = pos.col + dC[i];

            if (isInMat(v) && (!dp[v.lin][v.col] || dp[v.lin][v.col] && dp[pos.lin][pos.col] + mat[v.lin][v.col] < dp[v.lin][v.col])) {
                dp[v.lin][v.col] = dp[pos.lin][pos.col] + mat[v.lin][v.col];
                d.push(v);
            }
        }
    }

    fout << dp[m][n];
    solve(m, n, 0);

    fout.close();
    return 0;
}