Submission #917509

#	Time	Username	Problem	Language	Result	Execution time	Memory
917509		garamlee500	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	559 ms	118376 KiB

tracks

#include <iostream>
#include <deque>
#include <vector>
#include <limits>

using namespace std;
int maxY, maxX;

//bool visited[4000][4000] = {false};
int distances[4000][4000];
vector<string> grid;

pair<int, int> add(pair<int, int> a, pair<int, int> b){
    return make_pair(a.first+b.first,a.second+b.second);
}
bool valid(pair<int, int> a){
    if (a.first<0||a.first>=maxX||a.second<0||a.second>=maxY){
        return false;
    }

    return grid[a.second][a.first]!='.';

}


int getEdge(pair<int, int> a, pair<int, int> b){
    return grid[a.second][a.first] == grid[b.second][b.first] ? 0 : 1;

}


string s;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> maxY >> maxX;
    for (int i = 0; i < maxY; i++){
        cin >> s;
        grid.push_back(s);
        for (int j = 0; j < maxX; j++){
            distances[i][j] = numeric_limits<int>::max()/2;
        }
    }

    //visited[0][0] = false;
    deque<pair<int, int>> currents;
    int best = 0;
    distances[0][0] = 0;
    currents.emplace_back(0, 0);

    while (currents.size()>0){
        pair<int, int> current = currents.front();
        currents.pop_front();
        best = max(distances[current.second][current.first], best);
        pair<int, int> nextOne;


        nextOne = add(current, make_pair(1,0));
        if (valid(nextOne)){
            int newDistance = distances[current.second][current.first] + getEdge(current, nextOne);
            if (newDistance < distances[nextOne.second][nextOne.first]){
                distances[nextOne.second][nextOne.first] = newDistance;
                if (getEdge(current, nextOne)==0){
                    currents.push_front(nextOne);
                }
                else{
                    currents.push_back(nextOne);
                }

            }
        }

        nextOne = add(current, make_pair(-1,0));
        if (valid(nextOne)){
            int newDistance = distances[current.second][current.first] + getEdge(current, nextOne);
            if (newDistance < distances[nextOne.second][nextOne.first]){
                distances[nextOne.second][nextOne.first] = newDistance;
                if (getEdge(current, nextOne)==0){
                    currents.push_front(nextOne);
                }
                else{
                    currents.push_back(nextOne);
                }

            }
        }nextOne = add(current, make_pair(0,1));
        if (valid(nextOne)){
            int newDistance = distances[current.second][current.first] + getEdge(current, nextOne);
            if (newDistance < distances[nextOne.second][nextOne.first]){
                distances[nextOne.second][nextOne.first] = newDistance;
                if (getEdge(current, nextOne)==0){
                    currents.push_front(nextOne);
                }
                else{
                    currents.push_back(nextOne);
                }

            }
        }nextOne = add(current, make_pair(0,-1));
        if (valid(nextOne)){
            int newDistance = distances[current.second][current.first] + getEdge(current, nextOne);
            if (newDistance < distances[nextOne.second][nextOne.first]){
                distances[nextOne.second][nextOne.first] = newDistance;
                if (getEdge(current, nextOne)==0){
                    currents.push_front(nextOne);
                }
                else{
                    currents.push_back(nextOne);
                }

            }
        }
    }
    cout << best + 1;


}

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