Submission #1165528

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165528		goulthen	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	805 ms	430164 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define rep(i,a,b) for (int i = a; i <= b; ++i)
#define all(v) (v).begin(), (v).end()
 
const int MAXN = 4e3 + 10;
const int INF = 1e18;
const int MOD = 1e9 + 7;
int a[MAXN][MAXN], dist[MAXN][MAXN], seen[MAXN][MAXN];
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

void solve() {
    int n,m;
    cin >> n >> m;

    rep(i,1,n) {
        rep(j,1,m) {
            char ch;cin >> ch;
            a[i][j] = (ch == 'F' ? 1LL : ch == 'R' ? 2 : 0);
        }
    }

    deque<pii> q;
    q.push_back({1,1});
    seen[1][1] = 1;
    dist[1][1] = 1;
    int mx = 1;
    while (!q.empty()) {
        auto [x,y] = q.front();q.pop_front();

        rep(k,0,3) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 1 || ny < 1 || nx > n || ny > m || seen[nx][ny] || a[nx][ny] == 0) continue;
            seen[nx][ny] = 1;
            dist[nx][ny] = dist[x][y] + (a[x][y] != a[nx][ny]);
            mx = max(mx,dist[nx][ny]);
            //cout << nx << ' ' << ny << ' ' << dist[nx][ny] << ' ' << (a[x][y] == a[nx][ny]) << '\n';
            if (a[x][y] == a[nx][ny]) q.push_front({nx,ny});
            else q.push_back({nx,ny});
        }
    }
    cout << mx << '\n';
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int tt = 1;
    //cin >> tt;
    while (tt-- > 0) solve();
}

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