제출 #1150383

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150383		algo-cooker	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	782 ms	114596 KiB

tracks

#include<bits/stdc++.h>
#define f first
#define s second

using namespace std;
typedef long long ll;

int main(){
    ll h,w; cin >> h >> w;
    vector<vector<char>> mp(h, vector<char>(w));
    for(ll i=0; i<h; i++)
        for(ll j=0; j<w; j++)
            cin >> mp[i][j];

    deque<pair<ll,ll>> d;
    d.push_back({0,0});

    vector<vector<bool>> mark(h, vector<bool>(w, false));
    mark[0][0] = true;
    char tmp = mp[0][0];

    ll ans = 1;
    while(!d.empty()){
        auto v = d.back();
        d.pop_back();
        auto cv = mp[v.f][v.s];
        if(cv != tmp){
            tmp = cv;
            ans++;
        }

        if(v.f < h-1 && !mark[v.f+1][v.s]){
            mark[v.f+1][v.s] = true;
            if(mp[v.f+1][v.s] == cv) d.push_back({v.f+1, v.s});
            else if(mp[v.f+1][v.s] != '.') d.push_front({v.f+1, v.s});
        }

        if(v.s < w-1 && !mark[v.f][v.s+1]){
            mark[v.f][v.s+1] = true;
            if(mp[v.f][v.s+1] == cv) d.push_back({v.f, v.s+1});
            else if(mp[v.f][v.s+1] != '.') d.push_front({v.f, v.s+1});
        }

        if(v.f > 0 && !mark[v.f-1][v.s]){
            mark[v.f-1][v.s] = true;
            if(mp[v.f-1][v.s] == cv) d.push_back({v.f-1, v.s});
            else if(mp[v.f-1][v.s] != '.') d.push_front({v.f-1, v.s});
        }

        if(v.s > 0 && !mark[v.f][v.s-1]){
            mark[v.f][v.s-1] = true;
            if(mp[v.f][v.s-1] == cv) d.push_back({v.f, v.s-1});
            else if(mp[v.f][v.s-1] != '.') d.push_front({v.f, v.s-1});
        }
    }

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

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