제출 #913803

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
913803		enkhochir	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	440 ms	140004 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
string s[4005];
bool vis[4005][4005];
int ans=0;
int dx[4]={-1,1,0,0}, dy[4]={0,0,-1,1};
deque<pair<int,int>> q;
void solve(){
//	freopen("timeline.in","r",stdin);
//	freopen("timeline.out","w",stdout);
	cin>>n>>m;
	for(int i=0; i<n; i++){
		cin>>s[i];
	}
	vis[0][0]=1;
	q.push_back({0,0});
	char c=s[0][0];
	while(!q.empty()){
		int x=q.front().first, y=q.front().second;
		q.pop_front();
//		cout<<x<<" "<<y<<endl;
		if(s[x][y]!=c) ans++;
		c=s[x][y];
		for(int i=0; i<4; i++){
			int nx=x+dx[i], ny=y+dy[i];
			if(nx>=0 and nx<n and ny>=0 and ny<m and !vis[nx][ny] and s[nx][ny]!='.'){
				if(s[nx][ny]!=c){
					q.push_back({nx,ny});	
				}
				else{
					q.push_front({nx,ny});	
				}
				vis[nx][ny]=1;
			}
		}
	}
	cout<<ans+1<<endl;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	int t=1;
//	cin>>t;
	while(t--) solve();
}

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