Submission #778782

#	Time	Username	Problem	Language	Result	Execution time	Memory
778782		hasan_tawsif	Tracks in the Snow (BOI13_tracks)	C++17	2.19 / 100	476 ms	47304 KiB

tracks

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

int dx[] = {-1, +1, 0, 0};
int dy[] = {0, 0, +1, -1};

bool vis[4002][4002];
char adj[4002][4002];

void solve() {
	int n, m, cnt = 0, hasR = 0, hasF = 0; cin >> n >> m;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) cin >> adj[i][j], hasF |= adj[i][j] == 'F', hasR |= adj[i][j] == 'R';

	auto valid = [&](int r, int c) {
		return r <= n and r >= 1 and c <= m and c >= 1 and vis[r][c] == 0 and adj[r][c] != '.';
	};

	auto bfs = [&] (int r, int c) {
		queue<pair<int, int > > Q;
		Q.push({r, c});
		vis[r][c] = 1;
		while (!Q.empty()) {
			auto [R, C] = Q.front(); Q.pop();
			for (int i = 0; i < 4; ++i) {
				int nR = R + dx[i], nC = C + dy[i];
				if (valid(nR, nC) and adj[nR][nC] == adj[r][c]) {
					Q.push({nR, nC});
					vis[nR][nC] = 1;
				}
			}
		}
	};

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (vis[i][j] or adj[i][j] == '.' or adj[i][j] != adj[1][1]) continue;
			bfs(i, j);
			cnt++;
		}
	}
	cout << cnt + (hasF and hasR) << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1; 
//    cin >> t;
    while(t--) solve();
}

• Subtask 1: 0 / 30
• Subtask 2: 2.1875 / 70