Submission #876353

#	Time	Username	Problem	Language	Result	Execution time	Memory
876353		vjudge1	Tracks in the Snow (BOI13_tracks)	C++17	16.46 / 100	2124 ms	812824 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int MAXN = 4000 + 5;
char ch;
int n, m, ans;
int g[MAXN][MAXN];
bool seen[MAXN][MAXN];
queue<pair<int, int>> qq;

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		ch = getchar();
		for (int j = 1; j <= m; j++)
		{
			ch = getchar();
			switch (ch)
			{
			case 'R':
				g[i][j] = 0;
				break;
			case '.':
				g[i][j] = -1;
				break;
			case 'F':
				g[i][j] = 1;
				break;
			}
		}
	}
	while (true)
	{
		for (int i = 0; i <= n + 1; i++)
			for (int j = 0; j <= m + 1; j++)
				seen[i][j] = false;
		ans++;
		qq.push(make_pair(1, 1));
		while (!qq.empty())
		{
			pair<int, int> now = qq.front();
			qq.pop();
			int x = now.first, y = now.second;
			seen[x][y] = true;
			for (int i = 0; i < 4; i++)
			{
				int fx = x + dx[i], fy = y + dy[i];
				if (fx < 1 || fy < 1 || fx > n || fy > m || g[x][y] != g[fx][fy] || seen[fx][fy])
					continue;
				qq.push(make_pair(fx, fy));
			}
		}
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				if (seen[i][j])
					g[i][j] = 1 - g[i][j];
		bool ra = false, fo = false;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
			{
				if (g[i][j] == 0)
					ra = true;
				else if (g[i][j] == 1)
					fo = true;
			}
		if (!(ra && fo))
			break;
	}
	cout << ans + 1 << endl;
	return 0;
}

• Subtask 1: 3.3333333333333335 / 30
• Subtask 2: 13.125 / 70