#include <bits/stdc++.h>
#ifdef DEBUG
#include "debug.hpp"
#endif
using namespace std;
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define rep(i, N) for (int i = 0; i < (N); ++i)
#define rrep(i, N) for (int i = (N)-1; i >= 0; --i)
#define rep1(i, N) for (int i = 1; i <= (N); ++i)
#define rep2(i, s, e) for (int i = (s); i <= (e); ++i)
#ifdef DEBUG
#define debug(x...) \
do { \
++dbg::depth; \
string dbg_vals = dbg::to_string(x); \
--dbg::depth; \
dbg::fprint(__func__, __LINE__, #x, dbg_vals); \
} while (false)
#else
#define debug(...) 42
#endif
template<typename T> inline T& ckmin(T& a, T b) { return a = a > b ? b : a; }
template<typename T> inline T& ckmax(T& a, T b) { return a = a < b ? b : a; }
template<typename T, size_t dim> class tensor {
private:
vector<tensor<T, dim - 1>> v;
public:
template<typename... V>
tensor(size_t d, V... ds): v(d, tensor<T, dim - 1>(ds...)) {}
tensor<T, dim - 1>& operator[](size_t i) { return v[i]; }
size_t size() { return v.size(); }
auto begin() { return v.begin(); }
auto end() { return v.end(); }
};
template<typename T> class tensor<T, 0> {
private:
T v;
public:
tensor(T a = T{}): v{a} {}
operator T() { return v; }
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int H, W;
cin >> H >> W;
vector<string> grid(H);
rep(i, H) cin >> grid[i];
tensor<bool, 2> vis(H, W);
int ans{};
queue<pair<int, int>> a, b;
b.push({0, 0});
vis[0][0] = true;
auto check = [&](int i, int j, char c) -> void {
if (i < 0 || j < 0 || i >= H || j >= W) return;
if (grid[i][j] == '.' || vis[i][j]) return;
vis[i][j] = true;
if (grid[i][j] == c)
a.push({i, j});
else
b.push({i, j});
};
while (!b.empty()) {
++ans;
swap(a, b);
while (!a.empty()) {
auto [i, j] = a.front();
check(i + 1, j, grid[i][j]);
check(i - 1, j, grid[i][j]);
check(i, j + 1, grid[i][j]);
check(i, j - 1, grid[i][j]);
a.pop();
}
}
cout << ans << '\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
1092 KB |
Output is correct |
2 |
Correct |
0 ms |
308 KB |
Output is correct |
3 |
Correct |
1 ms |
312 KB |
Output is correct |
4 |
Correct |
5 ms |
884 KB |
Output is correct |
5 |
Correct |
2 ms |
596 KB |
Output is correct |
6 |
Correct |
0 ms |
208 KB |
Output is correct |
7 |
Correct |
1 ms |
308 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
320 KB |
Output is correct |
10 |
Correct |
2 ms |
452 KB |
Output is correct |
11 |
Correct |
2 ms |
452 KB |
Output is correct |
12 |
Correct |
5 ms |
564 KB |
Output is correct |
13 |
Correct |
2 ms |
588 KB |
Output is correct |
14 |
Correct |
2 ms |
560 KB |
Output is correct |
15 |
Correct |
10 ms |
1064 KB |
Output is correct |
16 |
Correct |
10 ms |
1080 KB |
Output is correct |
17 |
Correct |
7 ms |
972 KB |
Output is correct |
18 |
Correct |
5 ms |
844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
588 KB |
Output is correct |
2 |
Correct |
39 ms |
5092 KB |
Output is correct |
3 |
Correct |
168 ms |
49436 KB |
Output is correct |
4 |
Correct |
62 ms |
11572 KB |
Output is correct |
5 |
Correct |
136 ms |
27804 KB |
Output is correct |
6 |
Correct |
774 ms |
59604 KB |
Output is correct |
7 |
Correct |
2 ms |
588 KB |
Output is correct |
8 |
Correct |
2 ms |
588 KB |
Output is correct |
9 |
Correct |
2 ms |
460 KB |
Output is correct |
10 |
Correct |
1 ms |
324 KB |
Output is correct |
11 |
Correct |
2 ms |
600 KB |
Output is correct |
12 |
Correct |
1 ms |
328 KB |
Output is correct |
13 |
Correct |
34 ms |
4996 KB |
Output is correct |
14 |
Correct |
20 ms |
3048 KB |
Output is correct |
15 |
Correct |
11 ms |
3260 KB |
Output is correct |
16 |
Correct |
21 ms |
2264 KB |
Output is correct |
17 |
Correct |
105 ms |
12676 KB |
Output is correct |
18 |
Correct |
43 ms |
12424 KB |
Output is correct |
19 |
Correct |
46 ms |
11688 KB |
Output is correct |
20 |
Correct |
43 ms |
10736 KB |
Output is correct |
21 |
Correct |
104 ms |
28796 KB |
Output is correct |
22 |
Correct |
118 ms |
27716 KB |
Output is correct |
23 |
Correct |
211 ms |
24040 KB |
Output is correct |
24 |
Correct |
103 ms |
28040 KB |
Output is correct |
25 |
Correct |
213 ms |
49560 KB |
Output is correct |
26 |
Correct |
385 ms |
37908 KB |
Output is correct |
27 |
Correct |
499 ms |
51196 KB |
Output is correct |
28 |
Correct |
731 ms |
59608 KB |
Output is correct |
29 |
Correct |
744 ms |
58092 KB |
Output is correct |
30 |
Correct |
686 ms |
56352 KB |
Output is correct |
31 |
Correct |
577 ms |
32080 KB |
Output is correct |
32 |
Correct |
453 ms |
50216 KB |
Output is correct |