Submission #1018336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018336		cryptobunny	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	996 ms	122716 KiB

tracks

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

int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

int main() {
    int h, w;
    cin >> h >> w;
    vector<vector<char>> grid(h, vector<char>(w));
    int cnt = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> grid[i][j];
            if (grid[i][j] != '.') cnt++;
        }
    }
    deque<pair<int, int>> dq;
    vector<vector<int>> dist(h, vector<int>(w, 0x3f3f3f3f));
//    vector<vector<int>> vis(h, vector<int>(w));
    dist[0][0] = 0;
    dq.push_front({0, 0});
    while (!dq.empty()) {
        auto tp = dq.front();
        dq.pop_front();
//        cout << 61 - cnt << "\t" << tp.first << " " << tp.second << endl;
        cnt--;
        if (cnt == 0) {
            break;
        }
        for (int i = 0; i < 4; i++) {
            int nx = tp.first + dx[i];
            int ny = tp.second + dy[i];
            if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
            if (grid[nx][ny] == '.') continue;
            int cost = 1;
            if (grid[nx][ny] == grid[tp.first][tp.second]) cost = 0;
//            cout << vis[nx][ny] << "     " << nx << "  " << ny << endl;
            if (dist[tp.first][tp.second] + cost < dist[nx][ny]) {
//                vis[nx][ny] = true;
                dist[nx][ny] = dist[tp.first][tp.second] + cost;
                if (cost == 1) {
                    dq.push_back({nx, ny});
                } else {
                    dq.push_front({nx, ny});
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (grid[i][j] != '.') ans = max(ans, dist[i][j]);
        }
        cout << endl;
    }
    cout << ans + 1 << endl;
}

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