Submission #482112

#	Time	Username	Problem	Language	Result	Execution time	Memory
482112		nehasane	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	792 ms	166080 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
const int MAX_H = 4000;
const int MAX_W = 4000;
vector <string> meadow(MAX_H);
bool diff_animal(int x, int y, int diffx, int diffy){
    if (meadow[x][y] != meadow[x + diffx][y + diffy])
        return true;
    return false;
}
int main()
{
    int h, w;
    cin >> h >> w;
    for (int i = 0; i < h; i++)
        cin >> meadow[i];
    deque <tuple <int, int, int>> q;
    int dis[MAX_H][MAX_W];
    bool visited[MAX_H][MAX_W];
    for (int i = 0; i < MAX_H; i++){
        for (int j = 0; j < MAX_W; j++){
            dis[i][j] = INT_MAX;
            visited[i][j] = false;
        }
    }
    q.push_back({0, 0, 0});
    dis[0][0] = 0;
    int ans = 0;
    while (!q.empty()){
        int x = get<1>(q.front()), y = get<2>(q.front());
        q.pop_front();
        //check up
        if (x > 0 && meadow[x-1][y] != '.' && !visited[x-1][y]){
            int d = diff_animal(x, y, -1, 0);
            if (dis[x-1][y] > dis[x][y] + d){
                dis[x-1][y] = dis[x][y] + d;
                ans = max(ans, dis[x-1][y]);
                if (d == 0)
                    q.push_front({-dis[x-1][y], x-1, y});
                else
                    q.push_back({-dis[x-1][y], x-1, y});
                visited[x-1][y] = true;
            }
        }
        //check down
        if (x < h-1 && meadow[x+1][y] != '.' && !visited[x+1][y]){
            int d = diff_animal(x, y, 1, 0);
            if (dis[x+1][y] > dis[x][y] + d){
                dis[x+1][y] = dis[x][y] + d;
                ans = max(ans, dis[x+1][y]);
                if (d == 0)
                    q.push_front({-dis[x+1][y], x+1, y});
                else
                    q.push_back({-dis[x+1][y], x+1, y});
                visited[x+1][y] = true;
            }
        }
        //check left
        if (y > 0 && meadow[x][y-1] != '.' && !visited[x][y-1]){
            int d = diff_animal(x, y, 0, -1);
            if (dis[x][y-1] > dis[x][y] + d){
                dis[x][y-1] = dis[x][y] + d;
                ans = max(ans, dis[x][y-1]);
                if (d == 0)
                    q.push_front({-dis[x][y-1], x, y-1});
                else
                    q.push_back({-dis[x][y-1], x, y-1});
                visited[x][y-1] = true;
            }
        }
        //check right
        if (y < w-1 && meadow[x][y+1] != '.' && !visited[x][y+1]){
            int d = diff_animal(x, y, 0, 1);
            if (dis[x][y+1] > dis[x][y] + d){
                dis[x][y+1] = dis[x][y] + d;
                ans = max(ans, dis[x][y+1]);
                if (d == 0)
                    q.push_front({-dis[x][y+1], x, y+1});
                else
                    q.push_back({-dis[x][y+1], x, y+1});
                visited[x][y+1] = true;
            }
        }
    }
    cout << ans+ 1 << '\n';
}

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