Submission #1084180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084180		fonikos01	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	597 ms	222124 KiB

tracks

#include <bits/stdc++.h>
#include <vector>
#include <tuple>
// #include "debugging.h"
// #include <atcoder/lazysegtree>
// #include <atcoder/modint>
// #include <atcoder/dsu>

// #include <atcoder/segtree>
// using namespace atcoder;
// using mint = modint998244353;

using namespace std;
const int LARGE = 1e9;

#define all(x) (x).begin(), (x).end()

using ll = long long;
typedef pair<ll, ll> pi;

// bool cmp(pair<ll, ll> a, pair<ll, ll> b)
// {
//         if (a.second < b.second)
//                 return true;
//         return false;
// }
// struct node
// {
//         // part which will store data
//         int data;
//         // pointer to the previous node
//         struct node *prev;
//         // pointer to the next node
//         struct node *next;
// };
const int MOD = 1e9+7;
template<int MOD, int RT> struct mint {
	static const int mod = MOD;
	static constexpr mint rt() { return RT; } // primitive root
 	int v; 
 	explicit operator int() const { return v; } 
	mint():v(0) {}
	mint(ll _v):v(int(_v%MOD)) { v += (v<0)*MOD; }
	mint& operator+=(mint o) { 
		if ((v += o.v) >= MOD) v -= MOD; 
		return *this; }
	mint& operator-=(mint o) { 
		if ((v -= o.v) < 0) v += MOD; 
		return *this; }
	mint& operator*=(mint o) { 
		v = int((ll)v*o.v%MOD); return *this; }
	friend mint pow(mint a, ll p) { assert(p >= 0);
		return p==0?1:pow(a*a,p/2)*(p&1?a:1); }
	friend mint inv(mint a) { assert(a.v != 0); return pow(a,MOD-2); }
	friend mint operator+(mint a, mint b) { return a += b; }
	friend mint operator-(mint a, mint b) { return a -= b; }
	friend mint operator*(mint a, mint b) { return a *= b; }
};
using mi = mint<(int)MOD, 5>;

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

ll solve()
{
	ll H, W; cin >> H >> W;

	vector<string> A(H);
	for (int i = 0; i < H; i++) cin >> A[i];

	vector<vector<ll>> vis(H, vector<ll>(W));
	vis[0][0] = 1;
	char curr = A[0][0];
	deque<pair<ll,ll>> dq;
	dq.push_front(make_pair(0,0));
	vector<pair<ll,ll>> ut1 = {{0, 1}, {0, -1}, {1, 0}, {-1, 0},};
	ll ans = 1;

	while(!dq.empty()) {
		pair<ll,ll> temp = dq.front();
		dq.pop_front();
		ll i = temp.first, j = temp.second;
		if (A[i][j] != curr) {
			curr = A[i][j];
			ans++;
		}
		for (pair<ll,ll> utp : ut1) {
			ll newI = utp.first+i, newJ = utp.second+j;
			if (newI < 0 || newI >= H || newJ < 0 || newJ >= W || vis[newI][newJ] || A[newI][newJ] == '.') continue;
			vis[newI][newJ] = 1;
			if (A[newI][newJ] == curr) dq.push_front(make_pair(newI, newJ));
			else dq.push_back(make_pair(newI, newJ));
		}
	} 

	cout << ans << '\n';

	return 0;
}

int main()
{
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        // freopen("248.in", "r", stdin);
        // freopen("248.out", "w", stdout);

        // ll caseCnt = 1;


        // ll T;
        // cin >> T;
        // while (T--)
        // {
                
                solve();

                // 	cout << "Case #"<< caseCnt << ": " << ans << '\n';
                // 	caseCnt++;
        // }

        return 0;
}

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