#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
#define inin int
#define vi vector<int>
#define all(x) x.begin(), x.end()
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/
const inin N=1e3+2, M=3e5+10, mod=1e9+7;
bool com(vector<int> a, vector<int> b){
return abs(a[1]-a[0])<abs(b[1]-b[0]);
}
vector<int> mx = {1, -1, 0, 0}, my = {0, 0, 1, -1};
int h, w;
const int n = 4010;
vector<vector<char>> a(n, vector<char>(n, '.'));
vector<vector<int>> depth(n, vector<int>(n, 0));
bool isinside(int x, int y){
return (x>=0 && y>=0 && x<h && y<w && a[x][y]!='.');
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout<<setprecision(15)<<fixed;
cin>>h>>w;
for(int i=0; i<h; i++){
for(int j=0; j<w; j++){
cin>>a[i][j];
}
}
deque<pair<int, int>> d;
d.push_back({0, 0});
depth[0][0] = 1;
int ans = 0;
while(!d.empty()){
int x = d.front().first, y = d.front().second;
d.pop_front();
ans = max(ans, depth[x][y]);
for(int i=0; i<4; i++){
int xn = x+mx[i], yn = y+my[i];
if(isinside(xn, yn) && depth[xn][yn] == 0){
if(a[x][y] == a[xn][yn]){
depth[xn][yn] = depth[x][y];
d.push_front({xn, yn});
}else{
depth[xn][yn] = depth[x][y]+1;
d.push_back({xn, yn});
}
}
}
}
cout<<ans<<endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
46 ms |
79576 KB |
Output is correct |
2 |
Correct |
40 ms |
79272 KB |
Output is correct |
3 |
Correct |
40 ms |
79228 KB |
Output is correct |
4 |
Correct |
43 ms |
79576 KB |
Output is correct |
5 |
Correct |
36 ms |
79344 KB |
Output is correct |
6 |
Correct |
33 ms |
79204 KB |
Output is correct |
7 |
Correct |
34 ms |
79172 KB |
Output is correct |
8 |
Correct |
34 ms |
79248 KB |
Output is correct |
9 |
Correct |
36 ms |
79220 KB |
Output is correct |
10 |
Correct |
37 ms |
79244 KB |
Output is correct |
11 |
Correct |
42 ms |
79316 KB |
Output is correct |
12 |
Correct |
42 ms |
79308 KB |
Output is correct |
13 |
Correct |
50 ms |
79300 KB |
Output is correct |
14 |
Correct |
39 ms |
79364 KB |
Output is correct |
15 |
Correct |
47 ms |
79436 KB |
Output is correct |
16 |
Correct |
46 ms |
79580 KB |
Output is correct |
17 |
Correct |
45 ms |
79488 KB |
Output is correct |
18 |
Correct |
45 ms |
79564 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
36 ms |
79296 KB |
Output is correct |
2 |
Correct |
90 ms |
80728 KB |
Output is correct |
3 |
Correct |
481 ms |
91676 KB |
Output is correct |
4 |
Correct |
125 ms |
82960 KB |
Output is correct |
5 |
Correct |
281 ms |
88076 KB |
Output is correct |
6 |
Correct |
808 ms |
105316 KB |
Output is correct |
7 |
Correct |
37 ms |
79372 KB |
Output is correct |
8 |
Correct |
35 ms |
79300 KB |
Output is correct |
9 |
Correct |
36 ms |
79260 KB |
Output is correct |
10 |
Correct |
41 ms |
79324 KB |
Output is correct |
11 |
Correct |
36 ms |
79228 KB |
Output is correct |
12 |
Correct |
38 ms |
79308 KB |
Output is correct |
13 |
Correct |
84 ms |
80820 KB |
Output is correct |
14 |
Correct |
63 ms |
80168 KB |
Output is correct |
15 |
Correct |
62 ms |
80216 KB |
Output is correct |
16 |
Correct |
58 ms |
79896 KB |
Output is correct |
17 |
Correct |
178 ms |
83368 KB |
Output is correct |
18 |
Correct |
158 ms |
83140 KB |
Output is correct |
19 |
Correct |
127 ms |
82848 KB |
Output is correct |
20 |
Correct |
119 ms |
82656 KB |
Output is correct |
21 |
Correct |
264 ms |
88336 KB |
Output is correct |
22 |
Correct |
275 ms |
87972 KB |
Output is correct |
23 |
Correct |
320 ms |
87044 KB |
Output is correct |
24 |
Correct |
246 ms |
88176 KB |
Output is correct |
25 |
Correct |
559 ms |
91692 KB |
Output is correct |
26 |
Correct |
557 ms |
141552 KB |
Output is correct |
27 |
Correct |
703 ms |
119324 KB |
Output is correct |
28 |
Correct |
835 ms |
106264 KB |
Output is correct |
29 |
Correct |
813 ms |
104604 KB |
Output is correct |
30 |
Correct |
788 ms |
110360 KB |
Output is correct |
31 |
Correct |
614 ms |
89676 KB |
Output is correct |
32 |
Correct |
690 ms |
107884 KB |
Output is correct |