Submission #1148095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148095		moonbcw21	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	1064 ms	223788 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int maxn = 4010;
int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};
ll h, w, prof[maxn][maxn], resp = 1;
string neve[maxn];
bool dentro(ll novox, ll novoy){
    if(novox < 0) return false;
    if(novox >= h) return false;
    if(novoy < 0) return false;
    if(novoy >= w) return false;
    if(neve[novox][novoy] == '.') return false;
    return true;
}
int main(){
    cin >> h >> w;
    for(int i = 0; i < h; i++) cin >> neve[i];
    deque<pair<ll,ll>>q;
    q.push_back({0,0});
    prof[0][0] = 1;
    while(!q.empty()){
        ll atx = q.front().first, aty = q.front().second;
        q.pop_front();
        resp = max(resp,prof[atx][aty]);
        for(int i = 0; i < 4; i++){
            ll novox = atx+dx[i], novoy = aty+dy[i];
            if(dentro(novox,novoy) && !prof[novox][novoy]){
                if(neve[novox][novoy] == neve[atx][aty]){
                    prof[novox][novoy] = prof[atx][aty];
                    q.push_front({novox,novoy});
                }
                else{
                    prof[novox][novoy] = prof[atx][aty]+1;
                    q.push_back({novox,novoy});
                }
            }
        }
    }
    cout << resp << "\n";
    return 0;
}

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