제출 #556754

#제출 시각아이디문제언어결과실행 시간메모리
556754HanksburgerTracks in the Snow (BOI13_tracks)C++17
97.81 / 100
906 ms1048576 KiB
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define fi first
#define se second
pii dir[4]={{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vector<pii > vec, tmp;
char a[4003][4003];
int n, m, ans;
bool ok(pii u)
{
	return (u.fi && u.fi<=n && u.se && u.se<=m && a[u.fi][u.se]!='.');
}
void dfs(pii u)
{
	char x=a[u.fi][u.se];
	a[u.fi][u.se]='.';
	for (pii i:dir)
	{
		pii v=u;
		v.fi+=i.fi;
		v.se+=i.se;
		if (ok(v))
		{
			if (a[v.fi][v.se]==x)
				dfs(v);
			else
				tmp.push_back(v);
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i=1; i<=n; i++)
		for (int j=1; j<=m; j++)
			cin >> a[i][j];
	tmp.push_back({1, 1});
	while (!tmp.empty())
	{
		vec=tmp;
		tmp.clear();
		for (pii u:vec)
			dfs(u);
		ans++;
	}
	cout << ans;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...