Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- //#define int long long
- #define IOS ios::sync_with_stdio(false); cin.tie(0);
- //#include <ext/pb_ds/assoc_container.hpp>
- //using namespace __gnu_pbds;
- //typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
- std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
- const int INF = 1e9 + 7;
- const double EPS = 1e-10;
- const int MOD = 1e9 + 7;
- const int MAXN = 2e3 + 100;
- int n, m;
- char a[MAXN][MAXN];
- int dist[MAXN][MAXN];
- int dx[] = {-1, 0, 1, 0};
- int dy[] = {0, 1, 0, -1};
- inline void solve() {
- cin >> n >> m;
- pair<int, int> start;
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < m; ++j) {
- cin >> a[i][j];
- dist[i][j] = -1;
- if (a[i][j] == 'X') {
- start = {i, j};
- }
- }
- }
- int mx = 0, cnt = 0;
- bool odd = false, even = false;
- queue<pair<int, int>> q;
- q.push(start);
- dist[start.first][start.second] = 0;
- while (!q.empty()) {
- auto [i, j] = q.front();
- q.pop();
- if (a[i][j] == 'I') {
- odd |= (dist[i][j] % 2 == 0);
- even |= (dist[i][j] % 2 == 1);
- mx = max(mx, dist[i][j]);
- ++cnt;
- continue;
- }
- for (int k = 0; k < 4; ++k) {
- int x = i + dx[k], y = j + dy[k];
- if (x >= 0 && x < n && y >= 0 && y < m) {
- if (a[x][y] != 'B' && dist[x][y] == -1) {
- q.emplace(x, y);
- dist[x][y] = dist[i][j] + 1;
- }
- }
- }
- }
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < m; ++j) {
- if (a[i][j] == 'I' && dist[i][j] == -1) {
- cout << "-1\n";
- return;
- }
- }
- }
- if (odd && even) {
- cout << "-1\n";
- } else {
- cout << cnt * mx << '\n';
- }
- }
- int32_t main() {
- IOS;
- clock_t tStart = clock();
- int tt = 1;
- // cin >> tt;
- while (tt --> 0) {
- solve();
- }
- // cerr << "Runtime is:" << (long double) (clock() - tStart) / CLOCKS_PER_SEC << '\n';
- return 0;
- }
- /*
- 1. 数组开够了没
- 2. 文件名写对了没,文件夹建了吗
- 3. 内存会不会MLE
- 4. 多测清空?
- 5. 调试删干净了没
- 6. 取模有没有溢出
- 7. 快速幂底数要取模,幂对 mod-1 取模
- 8. 前向星和欧拉序要开2倍数组
- 9. 比较函数如果值相同的话有没有第二优先级
- 10. 线段树 4 倍空间,线段树合并和可持久化线段树 32 倍空间
- 11. 看清楚 log 的底数是啥,log后面的数是啥
- 12. long long 只有正负 2^63-1
- */
Advertisement
Add Comment
Please, Sign In to add comment