이 제출은 이전 버전의 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));
map<char, int> val;
val['.'] = 1;
val['F'] = 2;
val['R'] = 3;
for (int i = 0;i < N;i ++) {
for (int j = 0;j < M;j ++) {
char c;
cin >> c;
arr[i][j] = val[c];
}
}
assert (arr[0][0] == arr[N - 1][M - 1] && arr[0][0] > 1);
vector<int> X = {0, 0, 1, -1};
vector<int> Y = {1, -1, 0, 0};
vector<vector<int>> used(N, vector<int>(M, 0)), submx(N, vector<int>(M, 0));
map<array<int, 2>, vector<array<int, 2>>> g;
auto check = [&](int x, int y) -> bool {
if (x < 0 || x >= N || y < 0 || y >= M || used[x][y] == 1 || arr[x][y] <= 1) return 0;
return 1;
};
function<void(int, int, int, int)> dfs_init = [&](int sx, int sy, int _x, int _y) -> void {
used[sx][sy] = 1;
for (int i = 0;i < 4;i ++) if (check (X[i] + sx, Y[i] + sy) == true) {
if (arr[_x][_y] == arr[X[i] + sx][Y[i] + sy]) {
dfs_init (X[i] + sx, Y[i] + sy, _x, _y);
}
}
for (int i = 0;i < 4;i ++) if (check (X[i] + sx, Y[i] + sy) == true) {
if (arr[_x][_y] != arr[X[i] + sx][Y[i] + sy]) {
g[{_x, _y}].push_back({X[i] + sx, Y[i] + sy});
dfs_init (X[i] + sx, Y[i] + sy, X[i] + sx, Y[i] + sy);
}
}
};
dfs_init (0, 0, 0, 0);
function<void(int, int)> dfs = [&](int sx, int sy) -> void {
// cout << sx << " " << sy << " -- ";
// for (auto [vx, vy] : g[{sx, sy}]) {
// cout << vx << " " << vy << ", ";
// } cout << "\n";
for (auto [vx, vy] : g[{sx, sy}]) {
dfs (vx, vy);
submx[sx][sy] = max(submx[sx][sy], submx[vx][vy]);
}
submx[sx][sy] ++;
};
dfs (0, 0);
cout << submx[0][0] << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |