Submission #876372

#TimeUsernameProblemLanguageResultExecution timeMemory
876372vjudge1Tracks in the Snow (BOI13_tracks)C++17
0 / 100
968 ms1048576 KiB
#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 << v << endl;
	used[v] = 1;

	for(int u : adj[v]){
		if(used[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++){
			int v, u, u_;
			v = (i*w) + j;
			u = (i+1)*w + j;
			u_ = i*w + j + 1;

			if(tp[v] == '.') continue;
			
			if(i < (h-1) && tp[u] != '.'){
				adj[v].pb(u);
				adj[u].pb(v);
			}

			if(j < (w-1) && tp[u] != '.'){
				adj[v].pb(u_);
				adj[u_].pb(v);
			}
			
			tp[v] = 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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...