Submission #715912

#	Time	Username	Problem	Language	Result	Execution time	Memory
715912		Farbod	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1618 ms	1042932 KiB

tracks

/*
*  In the name of God
*
*  Author: Farbod Doost
*  Last Modified: Tue, 28 Mar 2023 (15:39:56)
*
*/
#include <bits/stdc++.h>
using namespace std;

const int N = 4005;

int n, m;
bool vis[N][N];
char a[N][N];

int T = 0;
deque <pair <short int, short int>> vec;

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

bool f(char a, char b)
{
    if (t)
        return a != b;
    return a == b;
}

bool val(short int &i, short int &j)
{
    return i >= 0 && i < n && j >= 0 && j < m && a[i][j] != '.' && !vis[i][j] && f(a[i][j], a[0][0]);
}

void dfs(short int x = 0, short int y = 0)
{
    vis[x][y] = 1, vec.push_back({x, y});
    for (short int i = 0; i < 4; i++) {
        short int nx = x + dx[i], ny = y + dy[i];
        if (val(nx, ny))
            dfs(nx, ny);
    }

    return;
}

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

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

    dfs();

    while (vec.size()) {
        int tmp = vec.size();

        t = 1 - t;
        for (int j = 0; j < vec.size(); j++) {
            short int x = vec[j].first, y = vec[j].second;
            for (short int i = 0; i < 4; i++) {
                short int nx = x + dx[i], ny = y + dy[i];
                if (val(nx, ny))
                    vec.push_back({nx, ny}), vis[nx][ny] = 1;
            }
        }

        while (tmp--)
            vec.pop_front();
        T++;
    }

    cout << T;

    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:63:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<short int, short int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for (int j = 0; j < vec.size(); j++) {
      |                         ~~^~~~~~~~~~~~

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