Submission #746783

#	Time	Username	Problem	Language	Result	Execution time	Memory
746783		Github	Tracks in the Snow (BOI13_tracks)	C++14	31.77 / 100	687 ms	239208 KiB

tracks

#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

#define speedup ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define ll long long
const int MAXN = 4010;

char grid[MAXN][MAXN];
int dist[MAXN][MAXN];
int dX[] = {1, -1, 0, 0};
int dY[] = {0, 0, 1, -1};
int h, w;

bool possibility(int x, int y){
    if (x >= 0 && x < h && y >= 0 && y < w && grid[x][y] != '.'){
        return true;
    }
    return false;
}

int main(){
    speedup
    cin >> h >> w;
    for (int i = 0; i < h; i++){
        string s; cin >> s;
        for (int j = 0; j < w; j++){
            grid[i][j] = s[j];
        }
    }
    deque<pair<int, int>> q;
    q.push_front({0, 0});
    memset(dist, -1, sizeof dist);
    dist[0][0] = 1;
    int ans = 1;
    while (!q.empty()){
        auto &[x, y] = q.front(); q.pop_front();
        for (int i = 0; i < 4; i++){
            int nX = x+dX[i], nY = y+dY[i];
            if (possibility(nX, nY) && dist[nX][nY] == -1){
                if (grid[nX][nY] == grid[x][y]){
                    dist[nX][nY] = dist[x][y];
                    q.push_front({nX, nY});
                }else{
                    dist[nX][nY] = dist[x][y]+1;
                    q.push_back({nX, nY});
                }
            }
        }
        ans = max(ans, dist[x][y]);
    }
    cout << ans << endl;
    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:42:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |         auto &[x, y] = q.front(); q.pop_front();
      |               ^

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