Submission #340047

#	Time	Username	Problem	Language	Result	Execution time	Memory
340047		sinamhdv	Zoo (COCI19_zoo)	C++11	110 / 110	56 ms	4332 KiB

zoo

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1000 * 1000 * 1000;
const ll LINF = (ll)INF * INF;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define msub(a, b) ((mod + ((ll)(a) - (b)) % mod) % mod)
#define mdiv(a, b) ((ll)(a) * poww((b), mod - 2) % mod)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 1100

vector<pii> ngb = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

int n, m;
char grid[MAXN][MAXN];
bool mark[MAXN][MAXN];
vector<pii> cur, nxt;
char clet;

void dfs(int x, int y)
{
	mark[x][y] = true;
	for (pii p : ngb)
	{
		int ux = x + p.fr;
		int uy = y + p.sc;
		if (ux >= n || ux < 0 || uy >= m || uy < 0)
		{
			continue;
		}
		if (mark[ux][uy] || grid[ux][uy] == '*')
		{
			continue;
		}
	
		if (grid[ux][uy] == clet)
		{
			dfs(ux, uy);
		}
		else
		{
			nxt.pb(mp(ux, uy));
		}
	}
}

int32_t main(void)
{
	fast_io;
	cin >> n >> m;
	FOR(i, 0, n)
	{
		FOR(j, 0, m)
		{
			cin >> grid[i][j];
		}
	}
	
	cur.pb(mp(0, 0));
	clet = grid[0][0];
	int ans = 0;
	while (!cur.empty())
	{
		ans++;
		for (pii v : cur)
		{
			if (!mark[v.fr][v.sc])
			{
				dfs(v.fr, v.sc);
			}
		}
		cur = nxt;
		nxt.clear();
		clet = (clet == 'B' ? 'T' : 'B');
	}

	cout << ans << endl;

	return 0;
}

• Subtask 1: 45 / 45
• Subtask 2: 65 / 65