이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
int L[] = {0, 0, 1, -1};
int R[] = {1, -1, 0, 0};
const int MXN = 4020;
int arr[MXN][MXN] = {0};
int dist[MXN][MXN] = {0};
int vis[MXN][MXN] = {0};
int h, w;
bool check(int a, int b){
if(a<1 || b<1 || a>h || b>w) return false;
else return true;
}
int main(){
//faster io
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>h>>w;
string str;
char c;
int a, b, n1, n2, mx;
for(int i=1; i<=h; i++){
cin>>str;
for(int j=1; j<=w; j++){
c = str[j-1];
if(c=='.') arr[i][j] = 0;
else if(c=='R') arr[i][j] = 1;
else arr[i][j] = 2;
}
}
deque<pii> q;
q.push_back({1,1});
dist[1][1] = 1;
while(!q.empty()){
a = q.front().first;
b = q.front().second;
q.pop_front();
for(int i=0; i<4; i++){
for(int j=0; j<4; j++){
n1 = a + L[i];
n2 = b + R[j];
if(check(n1, n2)){
if(arr[n1][n2]==0) continue;
if(!vis[n1][n2]){
if(arr[a][b]==arr[n1][n2]){
q.push_front({n1,n2});
dist[n1][n2] = dist[a][b];
}
else{
q.push_back({n1,n2});
dist[n1][n2] = dist[a][b] + 1;
}
}
}
}
}
vis[a][b] = 1;
}
mx = 0;
for(int i=1; i<=h; i++){
for(int j=1; j<=w; j++){
// cout<<dist[i][j]<<" ";
mx = max(mx, dist[i][j]);
}
// cout<<"\n";
}
cout<<mx<<"\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |