Submission #1083038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083038		PhamKhanhHuyen	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	612 ms	131012 KiB

tracks

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;

int h, w;
const int maxn = 4000;
char a[maxn + 3][maxn + 3];
int d[maxn + 3][maxn + 3];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

bool inside(int i, int j)
{
    return (i >= 1 && i <= h && j >= 1 && j <= w && a[i][j] != '.');
}

int main()
{
    //freopen("TRACK.INP", "r", stdin);
    //freopen("TRACK.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> h >> w;
    for(int i = 1; i <= h; i++)
    {
        for(int j = 1; j <= w; j++)
        {
            cin >> a[i][j];
        }
    }
    d[1][1] = 1;
    deque<pair<int,int>>dq;
    dq.push_front({1, 1});
    int ans = 1;
    while(!dq.empty())
    {
        pii p = dq.front();
        dq.pop_front();
        ans = max(ans, d[p.first][p.second]);
        for(int i = 0; i < 4; ++i)
        {
            int i1 = p.first + dx[i];
            int j1 = p.second + dy[i];
            if(inside(i1, j1) && d[i1][j1] == 0)
            {
                if(a[i1][j1] == a[p.first][p.second])
                {
                    d[i1][j1] = d[p.first][p.second];
                    dq.push_front({i1, j1});
                }
                else{
                    d[i1][j1] = d[p.first][p.second] + 1;
                    dq.push_back({i1, j1});
                }
            }
        }
    }
    cout << ans;
}

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