Advertisement
Dang_Quan_10_Tin

MAXR _BFS (Idea from Nguyen Nghia - Kien Giang TSTer)

Sep 28th, 2022
716
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.76 KB | None | 0 0
  1. #define task "MAXR"
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <queue>
  5.  
  6. using namespace std;
  7.  
  8. using ll = long long;
  9. using ld = long double;
  10. template <class T>
  11. void readInt(T &x)
  12. {
  13.     x = 0;
  14.     register int c;
  15.     while ((c = getchar()) && (c > '9' || c < '0'))
  16.         ;
  17.     for (; c >= '0' && c <= '9'; c = getchar())
  18.         x = x * 10 + c - '0';
  19. }
  20.  
  21. constexpr int N = 5e3 + 5;
  22. constexpr int Inf = 1e9 + 7;
  23. int x[] = {0, 0, -1, 1},
  24.     y[] = {-1, 1, 0, 0};
  25. int m, n;
  26. int a[N][N], d[N][N];
  27.  
  28. void Read()
  29. {
  30.     // cin >> m >> n;
  31.     readInt(m), readInt(n);
  32.  
  33.     for (int i = 1; i <= m; ++i)
  34.         for (int j = 1; j <= n; ++j)
  35.             // cin >> a[i][j];
  36.             readInt(a[i][j]);
  37. }
  38.  
  39. void Solve()
  40. {
  41.     fill_n(&d[0][0], N * N, Inf);
  42.  
  43.     queue<pair<int, int>> q;
  44.  
  45.     for (int i = 0; i <= m + 1; ++i)
  46.         for (int j = 0; j <= n + 1; ++j)
  47.             if (a[i][j] == 0)
  48.             {
  49.                 d[i][j] = 0;
  50.                 q.emplace(i, j);
  51.             }
  52.  
  53.     int ans(0);
  54.  
  55.     while (!q.empty())
  56.     {
  57.         pair<int, int> c = q.front();
  58.         q.pop();
  59.  
  60.         ans = max(ans, d[c.first][c.second] - 1);
  61.  
  62.         for (int i = 0; i < 4; ++i)
  63.         {
  64.             int u = c.first + x[i],
  65.                 v = c.second + y[i];
  66.  
  67.             if (u > 0 && u <= m && v > 0 && v <= n && d[u][v] == Inf)
  68.             {
  69.                 d[u][v] = d[c.first][c.second] + 1;
  70.                 q.emplace(u, v);
  71.             }
  72.         }
  73.     }
  74.  
  75.     cout << ans;
  76. }
  77.  
  78. int32_t main()
  79. {
  80.     ios_base::sync_with_stdio(0);
  81.     cin.tie(0);
  82.     cout.tie(0);
  83.  
  84.     if (fopen(task ".INP", "r"))
  85.     {
  86.         freopen(task ".INP", "r", stdin);
  87.         freopen(task ".OUT", "w", stdout);
  88.     }
  89.  
  90.     Read();
  91.     Solve();
  92. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement