Salvens

Untitled

Jan 17th, 2024
700
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.74 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. //#define int long long
  6.  
  7. #define IOS ios::sync_with_stdio(false); cin.tie(0);
  8.  
  9. //#include <ext/pb_ds/assoc_container.hpp>
  10. //using namespace __gnu_pbds;
  11. //typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  12. std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
  13.  
  14. const int INF = 1e9 + 7;
  15. const double EPS = 1e-10;
  16. const int MOD = 1e9 + 7;
  17. const int MAXN = 2e3 + 100;
  18.  
  19. int n, m;
  20. char a[MAXN][MAXN];
  21. int dist[MAXN][MAXN];
  22.  
  23. int dx[] = {-1, 0, 1, 0};
  24. int dy[] = {0, 1, 0, -1};
  25.  
  26. inline void solve() {
  27.     cin >> n >> m;
  28.     pair<int, int> start;
  29.     for (int i = 0; i < n; ++i) {
  30.         for (int j = 0; j < m; ++j) {
  31.             cin >> a[i][j];
  32.             dist[i][j] = -1;
  33.             if (a[i][j] == 'X') {
  34.                 start = {i, j};
  35.             }
  36.         }
  37.     }
  38.  
  39.     int mx = 0, cnt = 0;
  40.     bool odd = false, even = false;
  41.     queue<pair<int, int>> q;
  42.     q.push(start);
  43.     dist[start.first][start.second] = 0;
  44.     while (!q.empty()) {
  45.         auto [i, j] = q.front();
  46.         q.pop();
  47.         if (a[i][j] == 'I') {
  48.             odd |= (dist[i][j] % 2 == 0);
  49.             even |= (dist[i][j] % 2 == 1);
  50.             mx = max(mx, dist[i][j]);
  51.             ++cnt;
  52.             continue;
  53.         }
  54.         for (int k = 0; k < 4; ++k) {
  55.             int x = i + dx[k], y = j + dy[k];
  56.             if (x >= 0 && x < n && y >= 0 && y < m) {
  57.                 if (a[x][y] != 'B' && dist[x][y] == -1) {
  58.                     q.emplace(x, y);
  59.                     dist[x][y] = dist[i][j] + 1;
  60.                 }
  61.             }
  62.         }
  63.     }
  64.     for (int i = 0; i < n; ++i) {
  65.         for (int j = 0; j < m; ++j) {
  66.             if (a[i][j] == 'I' && dist[i][j] == -1) {
  67.                 cout << "-1\n";
  68.                 return;
  69.             }
  70.         }
  71.     }
  72.     if (odd && even) {
  73.         cout << "-1\n";
  74.     } else {
  75.         cout << cnt * mx << '\n';
  76.     }
  77. }
  78.  
  79.  
  80. int32_t main() {
  81.     IOS;
  82.     clock_t tStart = clock();
  83.  
  84.     int tt = 1;
  85. //    cin >> tt;
  86.     while (tt --> 0) {
  87.         solve();
  88.     }
  89. //    cerr << "Runtime is:" << (long double) (clock() - tStart) / CLOCKS_PER_SEC << '\n';
  90.     return 0;
  91. }
  92. /*
  93. 1.  数组开够了没
  94. 2.  文件名写对了没,文件夹建了吗
  95. 3.  内存会不会MLE
  96. 4.  多测清空?
  97. 5.  调试删干净了没
  98. 6.  取模有没有溢出
  99. 7.  快速幂底数要取模,幂对 mod-1 取模
  100. 8.  前向星和欧拉序要开2倍数组
  101. 9.  比较函数如果值相同的话有没有第二优先级
  102. 10. 线段树 4 倍空间,线段树合并和可持久化线段树 32 倍空间
  103. 11. 看清楚 log 的底数是啥,log后面的数是啥
  104. 12. long long 只有正负 2^63-1
  105. */
Advertisement
Add Comment
Please, Sign In to add comment