Submission #603274

#	Time	Username	Problem	Language	Result	Execution time	Memory
603274		jack715	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	402 ms	65628 KiB

tracks

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pp pop_back
#define mp make_pair
#define bb back
#define ff first
#define ss second

using namespace std;

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("tmp.in", "r", stdin);
    // freopen("tmp.out", "w", stdout);

    int H, W;
    cin >> H >> W;
    vector<string> grid(H);
    for (int i = 0; i < H; i++)
        cin >> grid[i];
    vector<vector<bool> > used(H, vector<bool>(W, 0));
    deque<pair<int, int> > q;
    q.push_back({0, 0});
    char last = '?';
    int ans = 0;
    pair<int, int> dir[4] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
    while (!q.empty()) {
        pair<int, int> now = q.front();
        q.pop_front();
        if (grid[now.ff][now.ss] != last) {
            ans++;
            last = grid[now.ff][now.ss];
        }

        for (pair<int, int> mv : dir) {
            if (now.ff+mv.ff < 0 || now.ff+mv.ff >= H) continue;
            if (now.ss+mv.ss < 0 || now.ss+mv.ss >= W) continue;
            if (used[now.ff+mv.ff][now.ss+mv.ss]) continue;
            if (grid[now.ff+mv.ff][now.ss+mv.ss] == '.') continue;

            if (grid[now.ff+mv.ff][now.ss+mv.ss] == grid[now.ff][now.ss])
                q.push_front({now.ff+mv.ff, now.ss+mv.ss});
            else 
                q.push_back({now.ff+mv.ff, now.ss+mv.ss});
            used[now.ff+mv.ff][now.ss+mv.ss] = 1;
        }
    }

    cout << ans << '\n';
    return 0;
}

/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
    * DON'T GET STUCK ON ONE APPROACH
*/

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