제출 #556758

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

tracks

#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[4001][4001];
int n, m, ans;
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 (v.fi && v.fi<=n && v.se && v.se<=m && 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 (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;
}

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