제출 #556761

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
556761		Hanksburger	Tracks in the Snow (BOI13_tracks)	C++17	80.31 / 100	828 ms	1048576 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define si short int
#define pii pair<si, si>
#define fi first
#define se second
pii dir[4]={{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vector<pii> vec, tmp;
string a[4001];
si n, m;
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 (a[v.fi][v.se]!='.')
		{
			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 (si i=0; i<=m+1; i++)
		a[0].push_back('.');
	for (si i=1; i<=n; i++)
	{
		a[i].push_back('.');
		for (si j=1; j<=m; j++)
		{
			char x;
			cin >> x;
			a[i].push_back(x);
		}
		a[i].push_back('.');
	}
	for (si i=0; i<=m+1; i++)
		a[n+1].push_back('.');
	int ans=0;
	tmp.push_back({1, 1});
	while (!tmp.empty())
	{
		vec=tmp;
		tmp.clear();
		for (pii u:vec)
			dfs(u);
		ans++;
	}
	cout << ans;
	return 0;
}

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