제출 #771273

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
771273		xCqlibur	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	607 ms	112284 KiB

tracks

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

#define ll long long

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int H, W, dx[4]{0, 1, 0, -1}, dy[4]{1, 0, -1, 0};
    cin >> H >> W;
    char grid[H][W];
    for(int i=0; i<H; ++i) {
        for(int j=0; j<W; ++j) {
            cin >> grid[i][j];
        }
    }
    deque<pair<int, int>> dq;
    int dist[H][W], ans=0;
    memset(dist, 0, sizeof(dist));
    dist[0][0]=1;
    dq.push_front({0, 0});
    while(!dq.empty()) {
        pair<int, int> p=dq.front();
        dq.pop_front();
        int r=p.first, c=p.second;
        ans=max(ans, dist[r][c]);
        for(int i=0; i<4; ++i) {
            int u=r+dx[i], v=c+dy[i];
            if(u<0||u>=H||v<0||v>=W||dist[u][v]||grid[u][v]=='.')
                continue;
            if(grid[u][v]!=grid[r][c]) {
                dist[u][v]=dist[r][c]+1;
                dq.push_back({u, v});
            }
            else {
                dist[u][v]=dist[r][c];
                dq.push_front({u, v});
            }
        }
    }
    cout << ans;
}

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