Submission #1187285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187285		pxsit	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	405 ms	89612 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const int INF = 1e9;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int h, w;
    cin >> h >> w;
    vector<string> adj(h);
    for (int i = 0; i < h; i++) cin >> adj[i];
    int n = h * w;
    vector<int> dis(n, INF);
    dis[0] = 0;
    deque<int> dq;
    dq.emplace_front(0);
    while (!dq.empty()){
        int id = dq.front();
        dq.pop_front();
        int d = dis[id];
        int x = id / w, y = id % w;
        for (int k = 0; k < 4; k++){
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 0 || nx >= h || ny < 0 || ny >= w || adj[nx][ny] == '.') continue;
            int nid = nx * w + ny;
            int wnw = adj[nx][ny] != adj[x][y];
            if (dis[nid] > d + wnw){
                dis[nid] = d + wnw;
                if (wnw == 0)
                    dq.emplace_front(nid);
                else
                    dq.emplace_back(nid);
            }
        }
    }
    int mx = 1;
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
            if (adj[i][j] != '.') mx = max(mx, dis[i * w + j]+1);
    cout << mx;
}

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