Submission #556870

#	Time	Username	Problem	Language	Result	Execution time	Memory
556870		Hanksburger	Tracks in the Snow (BOI13_tracks)	C++17	97.81 / 100	873 ms	1048576 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define si short 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 && a[v[0]][v[1]]!='.')
		{
			if (a[v[0]][v[1]]==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 (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;
}

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