BFS Algorithm: $O(N * M)$

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

using namespace std;

const int N = 1010;
int g[N][N], visited[N][N], m, n;

int main() {
  cin >> m >> n;

  string line;
  for (int i = 0; i < m; ++i) {
    cin >> line;
    for (int j = 0; j < n; ++j) g[i][j] = line[j] - '0';
  }

  memset(visited, 0, sizeof visited);

  queue<pair<int, int>> q;
  for (int y = 0; y < m; ++y)
    for (int x = 0; x < n; ++x)
      if (g[y][x] == 1) {
        q.emplace(x, y);
        visited[y][x] = 1;
      }

  static constexpr int dirs[] { 0, -1, 0, 1, 0};

  int steps = 0;
  while (not q.empty()) {
    size_t sz = q.size();
    while (sz--) {
      const auto [x, y] = q.front(); q.pop();
      g[y][x] = steps;
      for (int i = 0; i < 4; ++i) {
        int nx = x + dirs[i], ny = y + dirs[i + 1];
        if (nx < 0 || ny < 0 || nx == n || ny == m || visited[ny][nx])
          continue;
        q.emplace(nx, ny);
        visited[ny][nx] = 1; // mark as visted
      }
    }
    ++steps;
  }

  for (int y = 0; y < m; ++y) {
    for (int x = 0; x < n; ++x) printf("%d ", g[y][x]);
    printf("\n");
  }

  return 0;
}