#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[1009][1009],cnt,bo[1009][1009],dis[1000009];
string s;
vector <int> v[1000009];
deque <int> de;
void check(int q, int w, int rr);
void dfs(int q, int w);
void check(int q, int w, int rr){
if(q<1||q>a||w<1||w>b) return;
if(bo[q][w]!=0||f[q][w]!=rr) return;
dfs(q,w);
}
void dfs(int q, int w){
bo[q][w]=cnt;
check(q-1,w,f[q][w]);
check(q+1,w,f[q][w]);
check(q,w-1,f[q][w]);
check(q,w+1,f[q][w]);
}
void chk(int q, int w, int rr){
if(q<1||q>a||w<1||w>b) return;
if(bo[q][w]==0||bo[q][w]==rr) return;
v[bo[q][w]].push_back(rr);
v[rr].push_back(bo[q][w]);
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a>>b;
for(i=1; i<=a; i++){
cin>>s;
for(j=0; j<b; j++){
if(s[j]=='B'){
f[i][j+1]=1;
}
if(s[j]=='T'){
f[i][j+1]=2;
}
}
}
for(i=1; i<=a; i++){
for(j=1; j<=b; j++){
if(f[i][j]==0||bo[i][j]!=0) continue;
cnt++;
dfs(i,j);
}
}
for(i=1; i<=a; i++){
for(j=1; j<=b; j++){
if(bo[i][j]==0) continue;
chk(i-1,j,bo[i][j]);
chk(i+1,j,bo[i][j]);
chk(i,j-1,bo[i][j]);
chk(i,j+1,bo[i][j]);
}
}
de.push_back(bo[1][1]);
dis[bo[1][1]]=1;
zx=1;
while(de.size()){
c=de.front();
zx=max(zx,dis[c]);
de.pop_front();
for(vector <int>::iterator it=v[c].begin(); it!=v[c].end(); it++){
if(dis[(*it)]==0){
dis[(*it)]=dis[c]+1;
de.push_back((*it));
}
}
}
cout<<zx;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
23916 KB |
Output is correct |
| 2 |
Correct |
17 ms |
23916 KB |
Output is correct |
| 3 |
Correct |
17 ms |
24044 KB |
Output is correct |
| 4 |
Correct |
17 ms |
24300 KB |
Output is correct |
| 5 |
Correct |
18 ms |
24704 KB |
Output is correct |
| 6 |
Correct |
18 ms |
24684 KB |
Output is correct |
| 7 |
Correct |
18 ms |
24684 KB |
Output is correct |
| 8 |
Correct |
18 ms |
24688 KB |
Output is correct |
| 9 |
Correct |
18 ms |
24684 KB |
Output is correct |
| 10 |
Correct |
18 ms |
24812 KB |
Output is correct |
| 11 |
Correct |
18 ms |
24684 KB |
Output is correct |
| 12 |
Correct |
18 ms |
24812 KB |
Output is correct |
| 13 |
Correct |
18 ms |
24556 KB |
Output is correct |
| 14 |
Correct |
18 ms |
24684 KB |
Output is correct |
| 15 |
Correct |
18 ms |
24556 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
23916 KB |
Output is correct |
| 2 |
Correct |
17 ms |
23916 KB |
Output is correct |
| 3 |
Correct |
17 ms |
24044 KB |
Output is correct |
| 4 |
Correct |
17 ms |
24300 KB |
Output is correct |
| 5 |
Correct |
18 ms |
24704 KB |
Output is correct |
| 6 |
Correct |
18 ms |
24684 KB |
Output is correct |
| 7 |
Correct |
18 ms |
24684 KB |
Output is correct |
| 8 |
Correct |
18 ms |
24688 KB |
Output is correct |
| 9 |
Correct |
18 ms |
24684 KB |
Output is correct |
| 10 |
Correct |
18 ms |
24812 KB |
Output is correct |
| 11 |
Correct |
18 ms |
24684 KB |
Output is correct |
| 12 |
Correct |
18 ms |
24812 KB |
Output is correct |
| 13 |
Correct |
18 ms |
24556 KB |
Output is correct |
| 14 |
Correct |
18 ms |
24684 KB |
Output is correct |
| 15 |
Correct |
18 ms |
24556 KB |
Output is correct |
| 16 |
Correct |
38 ms |
33132 KB |
Output is correct |
| 17 |
Correct |
39 ms |
33260 KB |
Output is correct |
| 18 |
Correct |
41 ms |
33420 KB |
Output is correct |
| 19 |
Correct |
42 ms |
33388 KB |
Output is correct |
| 20 |
Correct |
38 ms |
33132 KB |
Output is correct |
| 21 |
Correct |
173 ms |
44780 KB |
Output is correct |
| 22 |
Correct |
172 ms |
44780 KB |
Output is correct |
| 23 |
Correct |
174 ms |
45036 KB |
Output is correct |
| 24 |
Correct |
180 ms |
45804 KB |
Output is correct |
| 25 |
Correct |
184 ms |
45676 KB |
Output is correct |
| 26 |
Correct |
175 ms |
45036 KB |
Output is correct |
| 27 |
Correct |
172 ms |
44780 KB |
Output is correct |
| 28 |
Correct |
164 ms |
44780 KB |
Output is correct |
| 29 |
Correct |
182 ms |
45856 KB |
Output is correct |
| 30 |
Correct |
179 ms |
45548 KB |
Output is correct |
