Submission #768876

#	Time	Username	Problem	Language	Result	Execution time	Memory
768876		1ne	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	412 ms	77536 KiB

tracks

/*
*  author : Apiram                  
*  created: 29.06.2023 01:16:40
*/

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

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n,m;cin>>n>>m;
	vector<int>dx = {-1,1,0,0};
	vector<int>dy = {0,0,-1,1};
	vector<string>arr(n);
	for (int i = 0;i<n;++i){
		cin>>arr[i];
	}
	deque<pair<int,int>>q;
	q.push_back({0,0});    
	vector<vector<bool>>visited(n,vector<bool>(m,0));
	visited[0][0] = 1;
	int ans = 1;
	char cur = arr[0][0];
	while(!q.empty()){
		auto u = q.back();
		q.pop_back();
		if (arr[u.first][u.second]!=cur){
			cur = arr[u.first][u.second];
			++ans;
		}
		for (int i = 0;i<4;++i){
			int nx = u.first + dx[i];
			int ny = u.second + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= m || arr[nx][ny] == '.' || visited[nx][ny])continue;
			visited[nx][ny] = true;
			if (arr[nx][ny] == arr[u.first][u.second]){
				q.push_back({nx,ny});
			}
			else{
				q.push_front({nx,ny});
			}
		}
	}
	cout<<ans<<'\n';		
	return 0;
}

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