제출 #1161218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161218		erlandmb	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	534 ms	212760 KiB

tracks

#include <iostream>
#include <tuple>
#include <set>
#include <map>
#include <bitset>
#include <vector>
#include <queue>
#include <cstring>
#include <stack>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <climits>
#include <unordered_map>
#include <unordered_set>
#include <cstdint>
#include <chrono>
#include <thread>
#include <omp.h>
#include <iomanip>
#include <numeric>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;
 
#define fastIO                   ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define pb                       push_back
#define mp                       make_pair
#define f                        first
#define s                        second
#define sz(a)                    (int)a.size()
#define all(a)                   (a).begin(), (a).end()
#define md(a, b)		         ((a) % b + b) % b
#define MOD(a)			         md(a, MOD)
#define mem(a, h)		         memset(a, (h), sizeof(a))
#define forn(i, n)			     for (int i = 0; i < n; i++)
#define fore(i, b, e)	         for (int i = b; i < e; i++)
#define forev(i, e, b)           for (int i = e; i > b; i--)
#define DBG(x)                   cerr<<#x<<" = "<<(x)<<endl
#define UNIQUE(x)                (x).resize(unique(all(x)) - (x).begin())
#define RAYA                     cout<<"=============================="<<'\n'
#define yes                      cout << "YES" << endl;
#define no                       cout << "NO" << endl;
#define PI                       acos(-1)
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
template <typename T>
istream &operator>>(istream &in, vector<T> &a) {
    for (auto &x : a) in >> x;
    return in;
}
template <typename T>
ostream &operator<<(ostream &out, vector<T> &a) {
    for (auto &x : a) out << x << " ";
    return out;
}
 
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
const int MOD = int(1e9) + 7;
 
ll mod(ll a) {return a >= MOD ? a - MOD : a;}
 
ll mod_mul(ll a, ll b) {return mod(a * b);}
 
ll mod_add(ll a, ll b) {return mod(a + b);}
 
ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b);}
 
ll lcm(ll a, ll b) {return (a * b) / gcd(a, b);}
 
ll exp(ll x, ll n) { if (n == 0) return 1; ll u = exp(x, n / 2); u = (u * u); if (n % 2 == 1) u = (u * x); return u; }
 
ll expmod(ll x, ll n) {if (n == 0) return 1 % MOD; ll u = expmod(x, n / 2); u = (u * u) % MOD; if (n & 1) u = (u * x) % MOD; return u; }
 
ll invmod(ll a){ return expmod(a, MOD - 2); }

int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};
ll n, m; 
vector<string> grid;

bool inside(ll x, ll y) {
    return x >= 0 && y >= 0 && x < n && y < m && grid[x][y] != '.';
}

void solve() {
    cin >> n >> m;
    grid.resize(n);
    forn (i, n) cin >> grid[i];
    vector<vector<ll>> depth(n, vll(m));
    depth[0][0] = 1;
    deque<pll> q;
    q.pb({0, 0});
    ll ans = 0;
    while (q.size()) {
        auto v = q.front(); q.pop_front();
        ans = max(ans, depth[v.f][v.s]);
        forn (i, 4) {
            ll x = v.f + dx[i], y = v.s + dy[i];
            if (inside(x, y) && depth[x][y] == 0) {
                if (grid[x][y] == grid[v.f][v.s]) {
                    depth[x][y] = depth[v.f][v.s];
                    q.push_front({x, y});
                } else {
                    depth[x][y] = depth[v.f][v.s] + 1;
                    q.push_back({x, y});
                }
            } 
        }
    }
    cout << ans << '\n';
}

int main() {
    fastIO;
    // cout << fixed;
    // cout << setprecision(10);
    // neighbors.assign(n, vll());
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}               

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