제출 #1178941

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1178941		punitt	Tracks in the Snow (BOI13_tracks)	C++20	27.40 / 100	868 ms	1114112 KiB

tracks

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

#define ll long long
#define pb push_back

void solve() {

	/*
		The component of starting index and every occurence of the other animal connected to this component will contritue at most 2 (1 if not other animal is present)
			Now other tham it, every component will contribute one each
	*/

	int n,m;
	cin >> n >> m;

	vector< string > mt(n);
	for( auto & e : mt )
		cin >> e;

	int ans = 1;
	bool first = true, ok = false;
	vector< vector<int> >vis(n, vector<int>(m));
	int dr[] = {-1,1,0,0};
	int dc[] = {0,0,-1,1};


	auto dfs = [&]( int x, int y, auto&dfs )->void{

		vis[x][y] = 1;
		for( int i = 0 ; i < 4 ; i++ ){
			int nr = x+dr[i];
			int nc = y+dc[i];
			if( nr >= 0 && nr < n && nc >= 0 && nc < m ){

				if( !vis[nr][nc] &&  mt[nr][nc] == mt[x][y]  )
					dfs( nr, nc, dfs );

				//  F se R mai krna hai, but R to only R 
				if( first ){
					if( !vis[nr][nc] && mt[nr][nc] != '.' &&  mt[nr][nc] != mt[x][y] && mt[x][y] == mt[0][0] ){
						ok = true;
						dfs(nr, nc, dfs );
					}
				}

			}
		}
		return;
	};


	dfs( 0,0, dfs );
	first = false;
	if( ok )
		ans++;

	for( int i = 0 ; i < n ; i++ ){
		for( int j = 0 ; j < m ; j++ ){
			if( mt[i][j] != '.' &&  !vis[i][j] ){
				dfs(i, j, dfs );
				ans++;
			}
		}
	}

	cout << ans << endl;

}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t = 1 ;
    // cin >> t;
    while (t--) 
        solve();
    return 0;
    
}

• Subtask 1: 3.3333 / 30
• Subtask 2: 24.0625 / 70