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