제출 #876349

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

tracks

#include <iostream>
#include <vector>

#define pb push_back
#define endl '\n'

using namespace std;

const int MAXN = 3e7+100;

vector<int> adj[MAXN];
char tp[MAXN];

int h, w, n;
string mat[4010];

int cnt;
bool used[MAXN];

void dfs(int v, int ld){
	// cout << ld << ' ' << v << endl;
	used[v] = 1;

	for(int u : adj[v]){
		if(used[u] || tp[u] == '.') continue;
		if(tp[u] == tp[v] || tp[u] == '-' || tp[v] == '-') dfs(u, ld);
		else if(tp[v] != '-'){
			adj[u].pb(n+ld);
			adj[n+ld].pb(u);

			// cout << u << "<->" << n+ld << endl;
		}
	}
}

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


	cin >> h >> w;
	n = h*w;

	for(int i=0;i<h; i++) cin >> mat[i];

	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			if(i < (h-1)){
				adj[(i*w) + j].pb((i+1)*w + j);
				adj[(i+1)*w + j].pb((i*w) + j);
			}

			if(j < (w-1)){
				adj[(i*w) + j].pb((i*w) +j+1);
				adj[(i*w) +j+1].pb((i*w) + j);
			}
			
			tp[i*w + j] = mat[i][j];
		}
	}

	for(int i=0; i<n; i++){
		if(used[i] || tp[i] == '.') continue;

		used[i] = 1;	
		tp[cnt + n] = '-';
		dfs(i, cnt);

		cnt++;

	}


	cout << cnt << endl;

	return 0;
}

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