제출 #768876

#제출 시각아이디문제언어결과실행 시간메모리
7688761neTracks in the Snow (BOI13_tracks)C++14
100 / 100
412 ms77536 KiB
/*
*  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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...