Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <utility>
- int const inf = int(1e9 + 7);
- bool IsOk(int x, int y, int n, int m) {
- return 0 <= x && x < n && 0 <= y && y < m;
- }
- int main() {
- int n, m;
- std::cin >> n >> m;
- std::vector<std::vector<int>>table(n, std::vector<int> (m));
- std::vector<std::vector<int>>results(n, std::vector<int> (m));
- std::queue<std::pair<int, int>> queue;
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- std::cin >> table[i][j];
- results[i][j] = table[i][j] ? 0 : inf;
- if (table[i][j]) {
- queue.emplace(i, j);
- }
- }
- }
- while (!queue.empty()) {
- auto [x, y] = queue.front();
- queue.pop();
- for (int i = -1; i <= 1; i++)
- for (int j = -1; j <= 1; j++) {
- if (abs(i) + abs(j) != 1) {
- continue;
- }
- if (IsOk(x + i, y + j, n, m)) {
- if (results[x + i][y + j] > results[x][y] + 1) {
- results[x + i][y + j] = results[x][y] + 1;
- queue.emplace(x + i, y + j);
- }
- }
- }
- }
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- std::cout << results[i][j] << " ";
- }
- std::cout << "\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement