제출 #1219387

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219387		vtnoo	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	474 ms	136192 KiB

tracks

/*
 * Se me ocurre ir desde el principio hasta el final marcando el camino que contenga la misma especie
 * y luego si es distinto aumentar la distancia a 1
 */
#include <bits/stdc++.h>
using namespace std;
#define forsn(i,s,n) for(int i=s; i<n; ++i)
#define forn(i,n) forsn(i,0,n)
#define pb push_back
#define snd second
#define fst first
#define all(x) x.begin(), x.end()
#define imp(x) for(auto __:x)cout<<__<<" "; cout<<endl;
#define sz(c) int((c).size())
using ll = long long;

const int inf=1e9;
struct Node{
	int x,y;
	char z;
};
int di[4]={1, -1, 0, 0};
int dj[4]={0, 0, 1, -1};

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
	int n,m;cin>>n>>m;
	vector<string> adj(n);
	forn(i,n){
		cin>>adj[i];
	}
	vector<vector<int>> dist(n, vector<int>(m, inf));
	deque<Node> q;
	q.pb({0, 0, adj[0][0]});
	dist[0][0]=0;
	auto safe=[&](int i, int j){
		return (i<n&&j<m&&i>=0&&j>=0&&adj[i][j]!='.');
	};
	while(!q.empty()){
		auto [i,j,c]=q.front();
		q.pop_front();
		forn(k,4){
			int ni=i+di[k], nj=j+dj[k];
			if(safe(ni, nj)){
				int w=(adj[ni][nj]!=c);
				if(dist[i][j]+w<dist[ni][nj]){
					dist[ni][nj]=dist[i][j]+w;
					if(w==0){
						q.push_front({ni,nj,adj[ni][nj]});
					}else{
						q.pb({ni,nj,adj[ni][nj]});
					}
				}
			}
		}
	}
	int ans=0;
	forn(i,n){
		forn(j,m){
			if(dist[i][j]==inf)continue;
			ans=max(ans, dist[i][j]);
		}
		cout<<endl;
	}
	cout<<ans+1<<endl;
}

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