Submission #1172178

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172178		ndan	Tracks in the Snow (BOI13_tracks)	C++20	0 / 100	2 ms	328 KiB

tracks

#include <bits/stdc++.h>
#include <deque>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define file "test"
#define forr(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define ford(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define forf(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define rep(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define MASK(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
const int maxn = 4e3 + 10;
const int MOD = 1e9 + 7; // 998244353 // 1e9 + 2277 // 1e9 + 5277
const ll inf = 1e18;
const int oo = 1e9 + 7;
const float eps = 1e-6;

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        }
        return 0;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        }
        return 0;
    }
/* END OF TEMPLATE. WHAT A SIGMA! TAKE A DEEP BREATH AND READY FOR CODING :D */

int h, w, d[maxn][maxn], ans;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
char a[maxn][maxn];

bool ok(int x, int y) {
    return x >= 1 && x <= h && y >= 1 && y <= w && a[x][y] != '.';
}

void bfs(int i, int j) {
    deque<pii> q;
    q.push_back(mp(i, j));
    d[i][j] = 1;
    while (q.size()) {
        pii curr = q.front();
        q.pop_front();
        ans = max(ans, d[curr.fi][curr.se]);
        forf(k, 0, 4) {
            int newi = curr.fi + dx[k];
            int newj = curr.se + dy[k];
            if (ok(newi, newj) && !d[newi][newj]) {
                if (a[curr.fi][curr.se] == a[newi][newj]) {
                    d[newi][newj] = d[curr.fi][curr.se];
                    q.push_front(mp(newi, newj));
                }
                else {
                    d[newi][newj] = d[curr.fi][curr.se] + 1;
                    q.push_back(mp(newi, newj));
                }
            }
        }
    }
    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen(file".inp", "r", stdin);
    freopen(file".out", "w", stdout);
#endif
    cin >> h >> w;
    forr(i, 1, h)
        forr(j, 1, w)
            cin >> a[i][j];
    bfs(1, 1);
    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:86:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |     freopen(file".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:87:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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