HA30_Subway(5)

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Manhattan {
private:
    int N, M;
    vector<vector<int> > grid;
    vector<vector<int> > distances;
    vector<vector<bool> > visited;

    // Смещения для перемещения вверх, вниз, влево и вправо
    int dx[4];
    int dy[4];

public:
    Manhattan(int n, int m, const vector<vector<int> >& input_grid) {
        N = n;
        M = m;
        grid = input_grid;
        distances.resize(N, vector<int>(M, -1));
        visited.resize(N, vector<bool>(M, false));

        // Инициализация смещений
        dx[0] = -1; dy[0] = 0;  // Вверх
        dx[1] = 1;  dy[1] = 0;  // Вниз
        dx[2] = 0;  dy[2] = -1; // Влево
        dx[3] = 0;  dy[3] = 1;  // Вправо
    }

    bool is_valid(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < M;
    }

    void BFS() {
        queue<pair<int, int> > q;

        // Инициализируем очередь ресторанами и устанавливаем расстояния до них равными 0
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                if (grid[i][j] == 1) {
                    q.push(make_pair(i, j));
                    distances[i][j] = 0;
                    visited[i][j] = true;
                }
            }
        }

        // Выполняем BFS
        while (!q.empty()) {
            pair<int, int> current = q.front();
            q.pop();
            int x = current.first;
            int y = current.second;

            for (int dir = 0; dir < 4; ++dir) {
                int nx = x + dx[dir];
                int ny = y + dy[dir];

                if (is_valid(nx, ny) && !visited[nx][ny]) {
                    distances[nx][ny] = distances[x][y] + 1;
                    visited[nx][ny] = true;
                    q.push(make_pair(nx, ny));
                }
            }
        }
    }

    void print_distances() {
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                cout << distances[i][j];
                if (j < M - 1) {
                    cout << " ";
                }
            }
            cout << endl;
        }
    }
};

int main() {
    int N, M;
    cin >> N >> M;

    vector<vector<int> > grid(N, vector<int>(M));

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cin >> grid[i][j];
        }
    }

    Manhattan manhattan(N, M, grid);
    manhattan.BFS();
    manhattan.print_distances();

    return 0;
}