제출 #625271

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

tracks

#include <bits/stdc++.h>
#include <iostream>
#define c(x) (cerr << __LINE__ << ": " << #x << ' ' << (x) << endl, (x))
#define vis() (cerr << __LINE__ << endl)
#define ll long long
#define f first
#define s second
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define mp make_pair

using namespace std;

vector<string> F;
vector<vector<int>> G;
vector<set<int>> A;
int N, M; 

bool ok(int I, int J){
	if(I < 0 || I >= N || J < 0 || J >= M) return false;
	return true;
}

void dfs(int I, int J, char a, int e){
	if(!ok(I, J)) return;
	if(F[I][J] != a || G[I][J]) return;

	G[I][J] = e;

	if(ok(I+1, J)){
		int b = G[I+1][J];
		if(b != 0 && b != e){
			A[b].insert(e);
			A[e].insert(b);
		}
	}
	
	if(ok(I, J+1)){
		int b = G[I][J+1];
		if(b != 0 && b != e){
			A[b].insert(e);
			A[e].insert(b);
		}
	}

	if(ok(I-1, J)){
		int b = G[I-1][J];
		if(b != 0 && b != e){
			A[b].insert(e);
			A[e].insert(b);
		}
	}

	if(ok(I, J-1)){
		int b = G[I][J-1];
		if(b != 0 && b != e){
			A[b].insert(e);
			A[e].insert(b);
		}
	}

	dfs(I+1, J, a, e);
	dfs(I, J+1, a, e);
	dfs(I-1, J, a, e);
	dfs(I, J-1, a, e);
}

int bfs(){
	int D = A.size();
	vector<bool> V(D);
	queue<pair<int, int>> q;
	q.push({1, 1});

	int ris = 0;
	while(!q.empty()){
		int n = q.front().f, d = q.front().s;
		q.pop();

		if(V[n]) continue;
		V[n] = true;

		ris = max(ris, d);

		for(int v: A[n]){
			q.push({v, d+1});
		}
	}

	return ris;
}

int main(){
	ifstream in("input.txt");
	ofstream out("output.txt");

	cin >> N >> M;

	F.resize(N);
	for(int i=0; i<N; i++){
		cin >> F[i];
	}
	

	G.resize(N, vector<int>(M, 0));

	A.pb(set<int>());
	int e = 1;
	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++){
			if(!G[i][j] && F[i][j] != '.'){
				A.pb(set<int>());
				dfs(i, j, F[0][j], e);
				e++;
			}
		}
	}
	

	cout << bfs();
}

• Subtask 1: 6.666666666666667 / 30
• Subtask 2: 10.9375 / 70