Submission #1256190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256190		attky	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	431 ms	125936 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

struct point {
    int x, y;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    char trace[n][m];
    int distance[n][m];

    for(int loop = 0; loop < n; ++loop) {
        for(int looping = 0; looping < m; ++looping) {
            cin >> trace[loop][looping];
            distance[loop][looping] = 1e9;
        }
    }

    char current;
    int num = 0;

    vector<point> stack;
    queue<point> q;

    distance[0][0] = 1;
    q.push({0, 0});

    while(q.size() > 0) {
        while(q.size() > 0) {
            stack.push_back(q.front());
            q.pop();
        }
        num++;
        current = trace[stack[0].x][stack[0].y];
        while(stack.size() > 0) {
            point enCours = stack.back();
            stack.pop_back();

            if(enCours.x > 0) {
                if(distance[enCours.x-1][enCours.y] == 1e9) {
                    if(trace[enCours.x-1][enCours.y] == current) {
                        stack.push_back({enCours.x-1, enCours.y});
                        distance[enCours.x-1][enCours.y] = num;
                    }
                    else if(trace[enCours.x-1][enCours.y] != '.') {
                        q.push({enCours.x-1, enCours.y});
                        distance[enCours.x-1][enCours.y] = num+1;
                    }
                }
            } 
            if(enCours.x < n-1) {
                if(distance[enCours.x+1][enCours.y] == 1e9) {
                    if(trace[enCours.x+1][enCours.y] == current) {
                        stack.push_back({enCours.x+1, enCours.y});
                        distance[enCours.x+1][enCours.y] = num;
                    }
                    else if(trace[enCours.x+1][enCours.y] != '.') {
                        q.push({enCours.x+1, enCours.y});
                        distance[enCours.x+1][enCours.y] = num+1;
                    }
                }
            } 
            if(enCours.y > 0) {
                if(distance[enCours.x][enCours.y-1] == 1e9) {
                    if(trace[enCours.x][enCours.y-1] == current) {
                        stack.push_back({enCours.x, enCours.y-1});
                        distance[enCours.x][enCours.y-1] = num;
                    }
                    else if(trace[enCours.x][enCours.y-1] != '.') {
                        q.push({enCours.x, enCours.y-1});
                        distance[enCours.x][enCours.y-1] = num+1;
                    }
                }
            } 
            if(enCours.y < m-1) {
                if(distance[enCours.x][enCours.y+1] == 1e9) {
                    if(trace[enCours.x][enCours.y+1] == current) {
                        stack.push_back({enCours.x, enCours.y+1});
                        distance[enCours.x][enCours.y+1] = num;
                    }
                    else if(trace[enCours.x][enCours.y+1] != '.') {
                        q.push({enCours.x, enCours.y+1});
                        distance[enCours.x][enCours.y+1] = num+1;
                    }
                }
            } 
        }
    }

    cout << num << '\n';
}

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