Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
