Submission #459602

#	Time	Username	Problem	Language	Result	Execution time	Memory
459602		chuangsheep	Tracks in the Snow (BOI13_tracks)	C++11	100 / 100	793 ms	124376 KiB

tracks

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

#define all(x) begin(x), end(x)
#define allr(x, r) begin(x), begin(x) + (r)
#define mp make_pair

using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

int xs[]{0, 1, 0, -1}, ys[]{-1, 0, 1, 0};

int main()
{
#if defined(DEBUG) && !defined(ONLINE_JUDGE)
    // DEBUG
    cerr << "DEBUG flag set - see test.out for output\n";
    freopen("/home/chuang/shared-drives/F:/repos/cp/ois/boi13/test.in", "r", stdin);
    freopen("/home/chuang/shared-drives/F:/repos/cp/ois/boi13/test.out", "w", stdout);
#else
    cin.tie(0)->sync_with_stdio(false);
#endif

    int H, W;
    cin >> H >> W;
    vector<vi> dist(H);
    for (auto &r : dist)
        r.assign(W, 0);
    dist[0][0] = 1;

    vector<string> grid(H);
    for (auto &r : grid)
        cin >> r;

    deque<pi> bfs;
    bfs.push_back(mp(0, 0));
    int ans = 1;
    while (!bfs.empty())
    {
        pi cell = bfs.front();
        bfs.pop_front();
        ans = max(ans, dist[cell.first][cell.second]);
        for (int i = 0; i < 4; i++)
        {
            int r = cell.first + xs[i];
            int c = cell.second + ys[i];
            if (r >= 0 && r < H && c >= 0 && c < W && grid[r][c] != '.' && dist[r][c] == 0)
            {
                if (grid[cell.first][cell.second] == grid[r][c])
                {
                    dist[r][c] = dist[cell.first][cell.second];
                    bfs.push_front(mp(r, c));
                }
                else
                {
                    dist[r][c] = dist[cell.first][cell.second] + 1;
                    bfs.push_back(mp(r, c));
                }
            }
        }
    }

    cout << ans << endl;
    return 0;
}

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