Submission #875565

#	Time	Username	Problem	Language	Result	Execution time	Memory
875565		12345678	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	708 ms	57424 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

const int N=4e3+5;
int h, w, cnt, dx[4]={1, 0, 0, -1}, dy[4]={0, 1, -1, 0};
char mp[N][N], c;
queue<pair<int, int>> q, nq;
bool vs[N][N];

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>h>>w;
    for (int i=1; i<=h; i++) for (int j=1; j<=w; j++) cin>>mp[i][j];
    nq.push({1, 1});
    vs[1][1]=1;
    while (!nq.empty())
    {
        cnt++;
        c=mp[nq.front().first][nq.front().second];
        while (!nq.empty()) q.push(nq.front()), nq.pop();
        while (!q.empty())
        {
            auto [x, y]=q.front();
            //cout<<cnt<<' '<<x<<' '<<y<<' '<<c<<'\n';
            q.pop();
            for (int i=0; i<4; i++)
            {
                int nx=x+dx[i], ny=y+dy[i];
                if (nx<1||nx>h||ny<1||ny>w||mp[nx][ny]=='.'||vs[nx][ny]) continue;
                vs[nx][ny]=1;
                if (mp[nx][ny]==c) q.push({nx, ny});
                else nq.push({nx, ny});
            }
        }
    }
    cout<<cnt;
}

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