Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- int const inf = int(1e9 + 7);
- pair<int, int> q[100 * 110];
- int us[110][110], a[110][110], n, m;
- int h, t;
- bool IsOk(int x, int y, int n) {
- return 1 <= x && x <= n && 1 <= y && y <= n;
- }
- void bfs(int i, int j) {
- if (!a[i][j])
- return;
- h = t = 0;
- q[t++] = {i, j};
- us[i][j] = 0;
- while (h < t) {
- int x = q[h].first, y = q[h++].second;
- 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)) {
- if (us[x + i][y + j] > us[x][y] + 1) {
- us[x + i][y + j] = us[x][y] + 1;
- q[t++] = {x + i, y + j};
- }
- }
- }
- }
- }
- int main() {
- std::cin >> n >> m;
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= m; j++) {
- std::cin >> a[i][j];
- us[i][j] = a[i][j] ? 0 : inf;
- }
- }
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= m; j++) {
- bfs(i, j);
- }
- }
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= m; j++) {
- std::cout << us[i][j] << " ";
- }
- std::cout << "\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement