Submission #555305

#	Time	Username	Problem	Language	Result	Execution time	Memory
555305		status_coding	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	824 ms	217420 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

struct pos
{
    int x, y, len;

    pos(int x, int y, int len)
    {
        this->x = x;
        this->y = y;
        this->len = len;
    }
};

int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

int n,m,ans;
char a[4005][4005];

int d[4005][4005];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

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

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            d[i][j] = -1;

    deque<pos> q;
    q.push_back(pos(1, 1, 1));

    while(!q.empty())
    {
        int x = q.front().x;
        int y = q.front().y;
        int len = q.front().len;
        q.pop_front();

        if(d[x][y] != -1)
            continue;

        d[x][y] = len;
        ans = len;

        for(int i=0; i<4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 1 || nx > n || ny < 1 || ny > m || d[nx][ny] != -1 || a[nx][ny] == '.')
                continue;

            if(a[x][y] == a[nx][ny])
                q.push_front(pos(nx, ny, len));
            else
                q.push_back(pos(nx, ny, len+1));
        }
    }

    cout<<ans;
    return 0;
}

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