621.cpp

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

struct Record {
    int dist, count, row, col;

    Record(int dist = 100000, int count = 0, int row = -1, int col = -1)
        : dist(dist)
        , count(count)
        , row(row)
        , col(col)
    { }

    Record& inc() {
        return ++dist, *this;
    }
};

Record combine(const Record& a, const Record& b) {
    if (a.row == b.row && a.col == b.col) {
        return a;
    } else if (a.dist > b.dist) {
        return b;
    } else if (a.dist < b.dist) {
        return a;
    } else {
        return Record(a.dist, a.count+b.count, -1, -1);
    }
}

int main() {
    freopen("input.txt", "rt", stdin);
    int n; scanf("%d", &n);
    std::vector<std::vector<int>> arr(n, std::vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%d", &arr[i][j]);
        }
    }

    std::vector<std::vector<Record>> best_l_u(n, std::vector<Record>(n));
    auto best_l_d = best_l_u;
    auto best_r_u = best_l_d;
    auto best_r_d = best_r_u;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (arr[i][j] != 0) {
                best_l_u[i][j] = Record(0, 1, i, j);
            } else if (i != 0 && j != 0) {
                best_l_u[i][j] = combine(best_l_u[i-1][j], best_l_u[i][j-1]).inc();
            } else if (i != 0) {
                best_l_u[i][j] = best_l_u[i-1][j].inc();
            } else if (j != 0) {
                best_l_u[i][j] = best_l_u[i][j-1].inc();
            }
        }
        for (int j = n-1; j >= 0; --j) {
            if (arr[i][j] != 0) {
                best_r_u[i][j] = Record(0, 1, i, j);
            } else if (i != 0 && j != n-1) {
                best_r_u[i][j] = combine(best_r_u[i][j+1], best_r_u[i-1][j]).inc();
            } else if (i != 0) {
                best_r_u[i][j] = best_r_u[i-1][j].inc();
            } else if (j != n-1) {
                best_r_u[i][j] = best_r_u[i][j+1].inc();
            }
        }
    }
    for (int i = n-1; i >= 0; --i) {
        for (int j = 0; j < n; ++j) {
            if (arr[i][j] != 0) {
                best_l_d[i][j] = Record(0, 1, i, j);
            } else if (i != n-1 && j != 0) {
                best_l_d[i][j] = combine(best_l_d[i+1][j], best_l_d[i][j-1]).inc();
            } else if (i != n-1) {
                best_l_d[i][j] = best_l_d[i+1][j].inc();
            } else if (j != 0) {
                best_l_d[i][j] = best_l_d[i][j-1].inc();
            }
        }
        for (int j = n-1; j >= 0; --j) {
            if (arr[i][j] != 0) {
                best_r_d[i][j] = Record(0, 1, i, j);
            } else if (i != n-1 && j != n-1) {
                best_r_d[i][j] = combine(best_r_d[i][j+1], best_r_d[i+1][j]).inc();
            } else if (i != n-1) {
                best_r_d[i][j] = best_r_d[i+1][j].inc();
            } else if (j != n-1) {
                best_r_d[i][j] = best_r_d[i][j+1].inc();
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (arr[i][j] != 0) continue;
            auto best = combine(
                combine(best_l_u[i][j], best_r_u[i][j]),
                combine(best_l_d[i][j], best_r_d[i][j])
            );
            if (best.count == 1) {
                arr[i][j] = arr[best.row][best.col];
            }
        }
    }
    for (auto& row : arr) {
        for (auto& it : row) printf("%d ", it);
        printf("\n");
    }

    return 0;
}