제출 #556872

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