Submission #1036996

#TimeUsernameProblemLanguageResultExecution timeMemory
1036996sssamuiTracks in the Snow (BOI13_tracks)C++17
2.19 / 100
139 ms34056 KiB
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;

vector<int> radd = { -1, 0, 1, 0 };
vector<int> cadd = { -1, 0, 1, 0 };

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int h, w;
	cin >> h >> w;
	vector<vector<char>> trk(h + 2, vector<char>(w + 2, '.'));
	for (int i = 1; i <= h; i++) for (int j = 1; j <= w; j++) cin >> trk[i][j];

	int ans = 0;
	vector<vector<bool>> vis(h + 2, vector<bool>(w + 2, false));
	if (trk[1][1] != '.')
	{
		queue<pair<int, int>> bfs;
		queue<pair<int, int>> nxt;
		bfs.push({ 1, 1 });
		vis[1][1] = true;
		while (!bfs.empty())
		{
			ans++;
			while (!bfs.empty())
			{
				int r = bfs.front().first, c = bfs.front().second;
				bfs.pop();
				for (int dir = 0; dir < 4; dir++) if (!vis[r + radd[dir]][c + cadd[dir]])
				{
					vis[r + radd[dir]][c + cadd[dir]] = true;
					if (trk[r + radd[dir]][c + cadd[dir]] == trk[r][c]) bfs.push({ r + radd[dir], c + cadd[dir] });
					else if (trk[r + radd[dir]][c + cadd[dir]] != '.') nxt.push({ r + radd[dir], c + cadd[dir] });
				}
			}
			
			while (!nxt.empty())
			{
				bfs.push(nxt.front());
				nxt.pop();
			}
		}
	}

	cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...