Submission #933565

#	Time	Username	Problem	Language	Result	Execution time	Memory
933565		KnowMayus	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	650 ms	134484 KiB

tracks

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
const int mx = 4005;
char  a[mx][mx];
deque<pair<int,int>>ok;
int dist[mx][mx];
//0/1 dfs, i do not understand the question lol.  If both R and F, are in the graph obviously, the minimum amount of animals is 2.
//no ? 
// if there is an appearance of 1, then its just 1.
//otherwise 0.
//How could they be more?

//THe above thought is debunked, upon looking at setups impossible.
//I was just thinking of the cases where the minimum was indeed 2, but that is not always the case.1

//if its the same track we want to visit it and clear it all before going to differing tracks.
int h,w;
bool ontrack(int x, int y ){
	return (x>=1)&&(y>=1)&&(x<=h)&&(y<=w)&&(a[x][y]!='.');
}

int main() {

cin>>h>>w;
for(int i=1;i<=h;i++){
	string s;
	cin>>s;
	for(int j=1;j<=w;j++){
		char g = s[j-1];
				a[i][j]=g;
				dist[i][j]=0;
	}
}
int ans = INT_MIN;
ok.push_front({1,1});
dist[1][1]=1;
while(!ok.empty()){
	int x = ok.front().first;
	int y = ok.front().second;
	ok.pop_front();
	ans = max(ans, dist[x][y]);
	//consider up down left right
	for(int i = -1;i<=1;i+=2){
		int nx = x + i;
	if(ontrack(nx,y)&&dist[nx][y]==0){
		//depth[x][y]==0 means not visited.
			//push the same tracks to priority.
			//to commit some sort of flood fill.
			if(a[x][y]==a[nx][y]){
				//same track/
							ok.push_front({nx,y});

				dist[nx][y]=dist[x][y];
			}else{
											ok.push_back({nx,y});

				dist[nx][y]=dist[x][y]+1;
			}
	}
	}
	for(int i=-1;i<=1;i+=2){
			int ny=y+i;
				if(ontrack(x,ny)&&dist[x][ny]==0){
		//dist[x][y]==0 means not visited.
		
			if(a[x][y]==a[x][ny]){
				//same track/'
											ok.push_front({x,ny});

				dist[x][ny]=dist[x][y];
			}else{
							ok.push_back({x,ny});
	//wait until all the last animals track connected components, are done running.
			//then this is as if the next layer of a bipartite tree.
				dist[x][ny]=dist[x][y]+1;
			}
	}
	}
}
cout<<ans<<"\n";

}

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