Submission #1126172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126172		Muhammet	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1061 ms	89308 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

int n, m, cn;

vector <vector <int>> vis;

vector <vector <char>> c;

int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);

	cin >> n >> m;
	c.resize(n+1, vector <char> (m+1));
	vis.assign(n+1, vector <int> (m+1,0));
	int cnt = 0;
	bool tr = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> c[i][j];
		}
	}
	int ans = 0;
	queue <pair<int,int>> q, q1;
	char a = c[1][1];
	q.push({1,1});
	while(!q.empty()){
		auto [x,y] = q.front();
		q.pop();
		if(x > 1 and c[x-1][y] == c[x][y] and !vis[x-1][y]){
			vis[x-1][y] = true;
			q.push({x-1,y});
		}
		if(x < n and c[x+1][y] == c[x][y] and !vis[x+1][y]){
			vis[x+1][y] = true;
			q.push({x+1,y});
		}
		if(y > 1 and c[x][y-1] == c[x][y] and !vis[x][y-1]){
			vis[x][y-1] = true;
			q.push({x,y-1});
		}
		if(y < m and c[x][y+1] == c[x][y] and !vis[x][y+1]){
			vis[x][y+1] = true;
			q.push({x,y+1});
		}
		if(x > 1 and c[x-1][y] != c[x][y] and c[x-1][y] != '.' and !vis[x-1][y]){
			vis[x-1][y] = true;
			q1.push({x-1,y});
		}
		if(x < n and c[x+1][y] != c[x][y] and c[x+1][y] != '.' and !vis[x+1][y]){
			vis[x+1][y] = true;
			q1.push({x+1,y});
		}
		if(y > 1 and c[x][y-1] != c[x][y] and c[x][y-1] != '.' and !vis[x][y-1]){
			vis[x][y-1] = true;
			q1.push({x,y-1});
		}
		if(y < m and c[x][y+1] != c[x][y] and c[x][y+1] != '.' and !vis[x][y+1]){
			vis[x][y+1] = true;
			q1.push({x,y+1});
		}
		if(q.empty()){
			ans++;
			while(!q1.empty()){
				q.push({q1.front()});
				q1.pop();
			}
		}
	}
	cout << ans;
}

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