Submission #938836

#	Time	Username	Problem	Language	Result	Execution time	Memory
938836		freedommo33	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	887 ms	123336 KiB

tracks

#include <bits/stdc++.h>

using namespace std;
constexpr int M = 4005;
int kolor[M][M];
char tab[M][M];
int spojna[M*4];
int xx[4] = {0, 0, -1, 1};
int yy[4] = {1, -1, 0, 0};
int n, m;

bool isValid(int x, int y){
	if(1>x || x>n) return 0;
	if(1>y || y>m) return 0;
	if(tab[x][y]=='.') return 0;
	if(kolor[x][y]!=0) return 0;
	return 1;
}
int maks = 0;
void bfs(){
	queue<pair<int, int>> q;
	queue<pair<pair<int, int>, int>> next;
	q.push({1, 1});
	kolor[1][1] = 1;
	while(!q.empty() || !next.empty()){
		int aktWart = 1;
		if(q.empty()==1){
			pair<int, int> temp = next.front().first;
			kolor[temp.first][temp.second] = next.front().second;
			next.pop();
			q.push(temp);
		}
		pair<int, int> p = q.front();
		aktWart = kolor[p.first][p.second];
		maks = max(maks, aktWart);
		q.pop();
		for(int i=0; i<4; i++){
			int nx = xx[i] + p.first;
			int ny = yy[i] + p.second;
			if(isValid(nx, ny)){
				if(tab[nx][ny]==tab[p.first][p.second]){
					kolor[nx][ny] = aktWart;
					q.push({nx, ny});
				}
				else{
					next.push({{nx, ny}, kolor[p.first][p.second] + 1});
				}
			}
		}
	}
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			cin>>tab[i][j];
		}
	}
	bfs();
	cout<<maks<<endl;
	return 0;
}

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