Submission #1206371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206371		sopaipilla	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	993 ms	411712 KiB

tracks

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
#define pf push_front
#define ppf pop_front
using namespace std;

int n, m;
vector<vi> grid, d, vst;
bool ok(int x, int y) {
    if(x<0 or x>=n or y<0 or y>=m) return true;
    if(!grid[x][y] or vst[x][y]) return true;
    vst[x][y]=1;
    return false;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    grid.resize(n,vi(m));
    for(int i=0; i<n; ++i) {
        string s;
        cin >> s;
        for(int j=0; j<m; ++j) {
            char c=s[j];
            if(c=='.') grid[i][j]=0;
            else if(c=='F') grid[i][j]=1;
            else grid[i][j]=2;
        }
    }
    
    vector<pii> p={{-1,0},{1,0},{0,-1},{0,1}};
    d.resize(n,vi(m));
    d[0][0]=1;

    deque<pii> prox;
    prox.pf({0,0});
    vst.resize(n,vi(m));
    vst[0][0]=1;

    int ans=1;
    while(!prox.empty()) {
        auto[x,y] = prox.front();
        prox.ppf();
        for(auto[dx,dy] : p) {
            if(ok(x+dx,y+dy)) continue;
            if(grid[x+dx][y+dy]==grid[x][y]) {
                prox.pf({x+dx,y+dy});
                d[x+dx][y+dy] = d[x][y];
            } else {
                prox.pb({x+dx,y+dy});
                d[x+dx][y+dy] = d[x][y]+1;
            }
            ans=max(ans,d[x+dx][y+dy]);
        }
    }
    cout << ans;
}

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