Submission #797533

#	Time	Username	Problem	Language	Result	Execution time	Memory
797533		bonk	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	923 ms	104704 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

const int N = 4002;
char grid[N][N];
int vis[N][N];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
int n, m;

bool ok(int x, int y){
    return (1 <= x && x <= n && 1 <= y && y <= m && vis[x][y] == -1);
}

int bfs(int sx, int sy){
    int ret = 1;
    queue<pair<int, int>>q, tmp; 
    q.emplace(sx, sy);
    vis[sx][sy] = 1;

    while(!q.empty()){
        auto [x, y] = q.front(); q.pop();
        ret = max(ret, vis[x][y]);
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(ok(nx, ny)){
                if(grid[nx][ny] == grid[x][y]){
                    q.emplace(nx, ny);
                    vis[nx][ny] = vis[x][y];
                } else if(grid[nx][ny] != '.'){
                    tmp.emplace(nx, ny);
                    vis[nx][ny] = vis[x][y] + 1;
                }
            }
        }

        if(q.empty()){
            while(!tmp.empty()){
                q.push(tmp.front());
                tmp.pop();
            }
        }
    }

    return ret;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    memset(vis, -1, sizeof(vis));
    cin >> n >> m;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++)
            cin >> grid[i][j];
    }

    cout << bfs(1, 1) << '\n';

    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'int bfs(int, int)':
tracks.cpp:23:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |         auto [x, y] = q.front(); q.pop();
      |              ^

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