이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;
const int INF = 10000000;
int n, m;
bool is_safe(int row, int col) {
return row >= 0 && row < n && col >= 0 && col < m;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
vector<vector<char>> grid(n, vector<char>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
vector<vector<int>> dist(n, vector<int>(m, INF));
dist[0][0] = 1;
deque<pii> q;
q.push_front({0, 0});
int dx[] = {0, 0, -1, 1}, dy[] = {1, -1, 0, 0};
while (!q.empty()) {
int row = q.front().first, col = q.front().second;
q.pop_front();
for (int i = 0; i < 4; i++) {
int dest_x = row + dx[i], dest_y = col + dy[i];
if (is_safe(dest_x, dest_y) && dist[dest_x][dest_y] == INF && grid[dest_x][dest_y] != '.') {
if (grid[dest_x][dest_y] != grid[row][col]) {
dist[dest_x][dest_y] = dist[row][col] + 1;
q.push_back({dest_x, dest_y});
} else {
dist[dest_x][dest_y] = dist[row][col];
q.push_front({dest_x, dest_y});
}
}
}
}
int ans = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (dist[i][j] != INF) ans = max(ans, dist[i][j]);
}
}
cout << ans << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |