Submission #989878

#	Time	Username	Problem	Language	Result	Execution time	Memory
989878		vjudge1	Tracks in the Snow (BOI13_tracks)	C++17	70.94 / 100	966 ms	227104 KiB

tracks

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

#define ff first
#define ss second
#define pb push_back

typedef long long ll;
typedef pair<int,int> pii;



const int S = 4000;
char meadow[S][S];
int dist[S][S];
bool vis[S][S];
const int INF = 1e8;

void reset(){
	for(int i = 0; i < S; i++){
		for(int j = 0; j < S; j++){
			dist[i][j] = INF;
		}
	}
}
int solve(int h, int w){

	reset();
	int ans = 0;
	pii start = {0,0};
	deque<pii> dq;
	dq.push_back(start);
	dist[0][0] = 0;
	while(dq.size()){
		auto [a, b] = dq.front(); dq.pop_front();
		
		if(vis[a][b]) continue;
		vis[a][b] = true;
		char animal = meadow[a][b];
		// obtener vecinos
		vector<pii> vecinos;
		if (a > 0){
			if(!vis[a-1][b]){
				pii up = {a-1, b};
				char animal_up = meadow[up.ff][up.ss];
				if(animal_up != '.'){
					vecinos.pb(up);
				}
			}
		}
		if(a < h-1){
			if(!vis[a+1][b]){
				pii down = {a+1, b};
				char animal_down = meadow[down.ff][down.ss];
				if(animal_down != '.'){
					vecinos.pb(down);
				}
			}			
		}
		if(b > 0){
			if(!vis[a][b-1]){
				pii left = {a, b-1};
				char animal_left = meadow[left.ff][left.ss];
				if(animal_left != '.'){
					vecinos.pb(left);
				}
			}			
		}
		if(b < h-1){
			if(!vis[a][b+1]){
				pii right = {a, b+1};
				char animal_right = meadow[right.ff][right.ss];
				if(animal_right != '.'){
					vecinos.pb(right);
				}
			}
		}
		
		// iterar por vecinos
		for(auto [x,y]: vecinos){
			int d = 0;
			if(meadow[x][y] != animal){
				d = 1;
			}
			// if (dist[curr_node] + d > dist[to]) continue;
			if(dist[a][b] + d > dist[x][y]) continue;
			
			dist[x][y] = dist[a][b] + d;
			
			ans = max(ans, dist[x][y]);
			
			if(d == 1){
				dq.push_back({x,y});
			}
			else if(d == 0){
				dq.push_front({x,y});
			}
		}
		
	}
	return ans;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  int h, w; cin >> h >> w;
  
  for(int i = 0; i < h; i++){
	  for(int j = 0; j < w; j++){
		  char x; cin >> x;
		  meadow[i][j] = x;
	  }
  }
  cout << solve(h,w)+1;
  
  
	  
  
}

• Subtask 1: 25 / 30
• Subtask 2: 45.9375 / 70