Submission #915112

#	Time	Username	Problem	Language	Result	Execution time	Memory
915112		Trytytka	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	871 ms	106960 KiB

tracks

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

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	int h, w;
	cin >> h >> w;
	vector<string> a(h);
	for (int i = 0; i < h; i++){
		cin >> a[i];
	}
	vector<vector<int>> b(h, vector<int>(w));
	queue<pair<int, int>> q;
	queue<pair<int, int>> p;
	q.push({0, 0});
	b[0][0]=1;
	int x, y;
	int s=0;
	while(q.size()){
		while(q.size()){
			x=q.front().first;
			y=q.front().second;
			q.pop();
			if(y-1>=0){
				if(b[x][y-1]==0){
					if(a[x][y-1]==a[x][y]) {q.push({x, y-1}); b[x][y-1]=1;}
					else if(a[x][y-1]!='.') {p.push({x, y-1}); b[x][y-1]=1;}
				}
			}
			if(y+1<w){
				if(b[x][y+1]==0){
					if(a[x][y+1]==a[x][y]) {q.push({x, y+1}); b[x][y+1]=1;}
					else if(a[x][y+1]!='.')  {p.push({x, y+1}); b[x][y+1]=1;}
				}
			}
			if(x-1>=0){
				if(b[x-1][y]==0){
					if(a[x-1][y]==a[x][y]) {q.push({x-1, y}); b[x-1][y]=1;}
					else if(a[x-1][y]!='.') {p.push({x-1, y}); b[x-1][y]=1;}
				}
			}
			if(x+1<h){
				if(b[x+1][y]==0){
					if(a[x+1][y]==a[x][y]) {q.push({x+1, y}); b[x+1][y]=1;}
					else if(a[x+1][y]!='.')  {p.push({x+1, y}); b[x+1][y]=1;}
				}
			}
		}
		swap(q, p);
		s++;
	}
	cout << s;
}

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