Advertisement
mfgnik

Untitled

Nov 25th, 2020
189
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.38 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5.  
  6. int const inf = int(1e9 + 7);
  7.  
  8.  
  9. pair<int, int> q[100 * 110];
  10. int us[110][110], a[110][110], n, m;
  11. int h, t;
  12.  
  13. bool IsOk(int x, int y, int n) {
  14. return 1 <= x && x <= n && 1 <= y && y <= n;
  15. }
  16.  
  17. void bfs(int i, int j) {
  18. if (!a[i][j])
  19. return;
  20. h = t = 0;
  21. q[t++] = {i, j};
  22. us[i][j] = 0;
  23. while (h < t) {
  24. int x = q[h].first, y = q[h++].second;
  25. for (int i = -1; i <= 1; i++)
  26. for (int j = -1; j <= 1; j++) {
  27. if (abs(i) + abs(j) != 1) {
  28. continue;
  29. }
  30. if (IsOk(x + i, y + j, n)) {
  31. if (us[x + i][y + j] > us[x][y] + 1) {
  32. us[x + i][y + j] = us[x][y] + 1;
  33. q[t++] = {x + i, y + j};
  34. }
  35. }
  36. }
  37. }
  38. }
  39.  
  40. int main() {
  41.  
  42. std::cin >> n >> m;
  43. for (int i = 1; i <= n; i++) {
  44. for (int j = 1; j <= m; j++) {
  45. std::cin >> a[i][j];
  46. us[i][j] = a[i][j] ? 0 : inf;
  47. }
  48. }
  49.  
  50.  
  51. for (int i = 1; i <= n; i++) {
  52. for (int j = 1; j <= m; j++) {
  53. bfs(i, j);
  54. }
  55. }
  56.  
  57.  
  58. for (int i = 1; i <= n; i++) {
  59. for (int j = 1; j <= m; j++) {
  60. std::cout << us[i][j] << " ";
  61. }
  62. std::cout << "\n";
  63. }
  64.  
  65. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement