Submission #897609

#	Time	Username	Problem	Language	Result	Execution time	Memory
897609		0xZero	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	780 ms	204364 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mx=4000;
char a[mx][mx];
bool vis[mx][mx];
int dist[mx][mx];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int n, m;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    memset(vis, 0, sizeof(vis));
    memset(dist, 0x3f, sizeof(dist));
    cin>>n>>m;
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>a[i][j];
    deque<pair<int, int>> q;
    q.push_front({0, 0});
    dist[0][0]=1;
    int mxd=0;
    while(!q.empty()){
        auto [x, y] = q.front();
        q.pop_front();
        if(vis[x][y])continue;
        vis[x][y]=1;
        mxd=max(mxd, dist[x][y]);
        for(int i=0;i<4;i++){
            int nx = x+dx[i], ny=y+dy[i];
            if(nx<0||ny<0||nx>=n||ny>=m)continue;
            if(vis[nx][ny])continue;
            if(a[nx][ny]=='.')continue;
            if(a[nx][ny]!=a[x][y])q.push_back({nx, ny}), dist[nx][ny]=dist[x][y]+1;
            else q.push_front({nx, ny}), dist[nx][ny]=dist[x][y];
        }
    }
    cout<<mxd;
    return 0;
}

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