제출 #1295230

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1295230		al95ireyiz	Tracks in the Snow (BOI13_tracks)	C++20	2.19 / 100	1072 ms	227868 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define len(x) (ll)x.size()
const ll INF = 1e9, INFL = 1e18;
const ll MOD = 1e9 + 7;
const ll maxn = 5000 + 5;
 
ll n, m, k = 0;

char a[maxn][maxn];
ll dis[maxn][maxn];
void _() {
    cin >> n >> m;
    ll c1 = 0, c2 = 0;
    for(ll i = 1; i <= n; i ++){
        for(ll j = 1; j <= m; j ++){
            cin >> a[i][j];
            dis[i][j] = INF;
            if(a[i][j] == 'F') c1 = 1;
            else if(a[i][j] == 'R') c2 = 1;
        }
    }
    deque<pair<ll, ll>>d;
    d.push_back({1, 1});
    dis[1][1] = 1;
    while(!d.empty()){
        auto [x, y] = d.front();
        d.pop_front();
        for(auto [i, j] : vector<pair<ll, ll>>{{x - 1, y}, {x, y - 1}, {x + 1, y}, {x, y + 1}}){
            if(i <= 0 or j <= 0 or i > n or j > m) continue;
            if(a[i][j] == '.') continue;
            if(dis[i][j] > dis[x][y] + (a[x][y] != a[i][j])){
                dis[i][j] = dis[x][y] + (a[x][y] != a[i][j]);
                if(a[x][y] != a[i][j]) d.push_back({i, j});
                else d.push_front({i, j});
            }
        }
    }
    cout << max(dis[n][m], c1 + c2) << '\n';
}
signed main() {
    cin.tie(0)->sync_with_stdio(0);
    ll t = 1;
    // cin >> t;
    while(t --) _();
}

• Subtask 1: 0 / 30
• Subtask 2: 2.1875 / 70