Submission #482134

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

tracks

#include <bits/stdc++.h>
using namespace std;
const int MAX_H = 4000;
const int MAX_W = 4000;

vector <string> meadow(MAX_H);
int dis[MAX_H][MAX_W];
bool visited[MAX_H][MAX_W];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

bool diff_animal(int x, int y, int diffx, int diffy){
    if (meadow[x][y] != meadow[x + diffx][y + diffy])
        return true;
    return false;
}
bool valid_sq(int x, int y, int h, int w){
    if (x >= 0 && x < h && y >= 0 && y < w && meadow[x][y] != '.')
        return true;
    return false;
}

int main()
{
    int h, w;
    cin >> h >> w;
    for (int i = 0; i < h; i++)
        cin >> meadow[i];
    deque <pair <int, int>> q;
    memset(dis, -1, sizeof(dis));
    int ans = 0;
    dis[0][0] = 0;
    q.push_back({0, 0});
    while (!q.empty()){
        int x = q.front().first, y = q.front().second;
        q.pop_front();
        ans = max(ans, dis[x][y]);
        for (int i = 0; i < 4; i++){
            int curr_x = x + dx[i], curr_y = y + dy[i];
            if (valid_sq(curr_x, curr_y, h, w) && dis[curr_x][curr_y] == -1){
                int d = diff_animal(x, y, dx[i], dy[i]);
                dis[curr_x][curr_y] = dis[x][y] + d;
                if (d == 0)
                    q.push_front({curr_x, curr_y});
                else
                    q.push_back({curr_x, curr_y});
            }
        }
    }
    cout << ans + 1 << '\n';
}

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