| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1333022 | kantaponz | Tracks in the Snow (BOI13_tracks) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx = 4005;
ll dist[nx][nx];
int H, W;
int grid[nx][nx];
bool vis[nx][nx];
int xx[4] = {0, -1, 0, 1};
int yy[4] = {1, 0, -1, 0};
priority_queue<tuple<ll,int,int>> pq;
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> H >> W;
for (int i = 1; i <= H; i++) {
for (int j = 1; j <= W; j++) {
char c; cin >> c;
dist[i][j] = 1e18;
if (c == 'R') grid[i][j] = 1;
else if (c == 'F') grid[i][j] = 0;
else if (c == '.') grid[i][j] = -1;
}
}
dist[1][1] = 1;
pq.emplace(1, 1, 1);
while (!pq.empty()) {
auto [w, y, x] = pq.top();
pq.pop();
if (dist[y][x] < w) continue;
for (int i = 0; i < 4; i++) {
int ny = y + yy[i], nx = x + xx[i];
if (ny < 1 || ny > H || nx < 1 || nx > W) continue;
if (grid[ny][nx] == -1) continue;
if (grid[ny][nx] == grid[y][x]) {
if (dist[ny][nx] <= w) continue;
dist[ny][nx] = w;
pq.emplace(w, ny, nx);
}
if (dist[ny][nx] <= w + 1) continue;
dist[ny][nx] = w + 1;
pq.emplace(w + 1, ny, nx);
}
}
ll ans = 0;
for (int i = 1; i <= H; i++) {
for (int j = 1; j <= W; j++) {
if (grid[i][j] == -1) continue;
ans = max(ans, dist[i][j]);
}
}
/*for (int i = 1; i <= H; i++) {
for (int j = 1; j <= W; j++) {
cout << dist[i][j] << " ";
}
cout << endl;
}*/
cout << ans;
}
/*
5 5
FFFFF
RFRRR
RF..R
RF..R
RFFFF
*/