이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int32_t main () {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N, M;
cin >> N >> M;
vector<vector<int>> arr(N, vector<int>(M));
vector<int> X = {0, 0, -1, 1};
vector<int> Y = {1, -1, 0, 0};
for (int i = 0;i < N;i ++) {
for (int j = 0;j < M;j ++) {
char c;
cin >> c;
arr[i][j] = (c == '.' ? -1 : (c == 'R' ? 0 : 1));
}
}
// for (int i = 0;i < N;i ++) {
// for (int j = 0;j < M;j ++) {
// cout << arr[i][j] << " ";
// } cout << "\n";
// } cout << "\n";
vector<vector<int>> dist(N, vector<int>(M, 0));
dist[0][0] = 1;
deque<array<int, 3>> q;
q.push_back({0, 0, 1});
auto check = [&](int x, int y) -> bool {
if (x >= N || y >= M || x < 0 || y < 0 || arr[x][y] == -1 || dist[x][y] != 0) return 0;
return 1;
};
int ans = 1;
while (q.size() > 0) {
auto [sx, sy, cnt] = q.front();
q.pop_front();
ans = max(ans, cnt);
for (int t = 0;t < 4;t ++) {
int vx = sx + X[t];
int vy = sy + Y[t];
if (check (vx, vy)) {
if (arr[vx][vy] == arr[sx][sy]) {
dist[vx][vy] = cnt;
q.push_front ({vx, vy, dist[vx][vy]});
} else {
dist[vx][vy] = cnt + 1;
q.push_back ({vx, vy, dist[vx][vy]});
}
}
}
}
cout << ans << "\n";
// for (int i = 0;i < N;i ++) {
// for (int j = 0;j < M;j ++) {
// cout << dist[i][j] << " ";
// } cout << "\n";
// } cout << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |