이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pr pair<ll, ll>
#define f first
#define s second
#define pb push_back
const int ndim=4001;
int ns;
vector<vector<int>> d(ndim, vector<int>(ndim));
map<pr, int> ms;
vector<vector<bool>> vis(ndim, vector<bool>(ndim, false));
vector<set<int>> adj(2e5);
int h, w;
int dx[4]={1, -1, 0, 0};
int dy[4]={0, 0, 1, -1};
void dfs(int x, int y, int col, int num){
if(x<0 || x>=h || y<0 || y>=w ) return;
if(d[x][y]!=col || vis[x][y]) return;
//cout<<" x/y= "<<x<<" "<<y<<endl;
ms[{x,y}]=num;
vis[x][y]=true;
for (int i=0; i<4; i++){
int xn=x+dx[i]; int yn=y+dy[i];
dfs(xn, yn, col, num);
}
}
void dfs1(int x, int y, int col, int num){
if(x<0 || x>=h || y<0 || y>=w ) return;
if(d[x][y]!=col || vis[x][y]) return;
//cout<<" x/y= "<<x<<" "<<y<<endl;
vis[x][y]=true;
for (int i=0; i<4; i++){
int xn=x+dx[i]; int yn=y+dy[i];
if(xn<0 || xn>=h || yn<0 || yn>=w ) continue;
if(d[xn][yn]==-1) continue;
if(d[xn][yn]!=d[x][y]){
adj[ms[{xn, yn}]].insert(ms[{x, y}]);
adj[ms[{x, y}]].insert(ms[{xn, yn}]);
}
dfs1(xn, yn, col, num);
}
}
int main(){
cin>>h>>w;
//vector<vector<int>> d(h, vector<int> (w, -1));
int nf=0;
for (int i=0; i<h; i++){
string s; cin>>s;
for (int j=0; j<w; j++){
if(s[j]=='.') {
d[i][j]=-1; continue;
}
nf++;
if(s[j]=='R') d[i][j]=0;
else d[i][j]=1;
}
}
//for (int i=0; i<h; i++){
// for (int j=0; j<w; j++) cout<<d[i][j]<<" ";
// cout<<endl;
//}
int num=0;
for (int i=0; i<h; i++){
for (int j=0; j<w; j++){
if((d[i][j]!=-1) & (!vis[i][j])) {
dfs(i, j, d[i][j], num);
num++;
}
}
}
//cout<<" we are here"<<endl;
//==============
for (int i=0; i<h; i++){
for (int j=0; j<w; j++) vis[i][j]=false;
}
for (int i=0; i<h; i++){
for (int j=0; j<w; j++){
if((d[i][j]!=-1) & (!vis[i][j])) {
dfs1(i, j, d[i][j], num);
}
}
}
//cout<<" we are here"<<endl;
//for (int i=0; i<num; i++) {
// for (auto e: adj[i]) cout<<e<<" ";
// cout<<endl;
//}
vector<bool> vis1(num, false);
vector<int> level(num, -1);
queue<pr> q; q.push({0, 0}); // node, lev
level[0]=0;
int lv_max=0;
while (!q.empty()){
pr nd=q.front(); q.pop();
int node=nd.f; int lev=nd.s;
for (int elem: adj[node]){
//cout<<" elem= "<<elem<<endl;
if(level[elem]==-1){
level[elem]=lev+1; q.push({elem, lev+1});
lv_max=max(lv_max, lev+1);
}
}
}
cout<<lv_max+1<<endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |