Submission #1032554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032554		hippo123	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	641 ms	138492 KiB

tracks

#include <bits/stdc++.h>
 
using namespace std;
#define ll long long
#define pr pair<int, int>
#define f first
#define s second
#define pb push_back
const int ndim=4001;
int ns;
string mps[ndim];
vector<vector<int>> level(ndim, vector<int> (ndim, -1));



int h, w; 

	int dx[4]={1, -1, 0, 0}; 
	int dy[4]={0, 0, 1, -1};

bool check(int x, int y){
	if(x>=0 && x<h && y>=0 && y<w && mps[x][y]!='.') return true;
	else return false; 
}

int main(){
	cin>>h>>w;
	for (int i=0; i<h; i++) cin>>mps[i];

	deque<pr> q; 
	q.push_front({0, 0}); // x, y
	level[0][0]=1;
	int ans=0;
	while(!q.empty()){
		pr nd=q.front(); q.pop_front();
		ans=max(ans, level[nd.f][nd.s]);
		for (int i=0; i<4; i++){
			int x=nd.f+dx[i]; int y=nd.s+dy[i];
			if(check(x, y) && level[x][y]==-1){
				if(mps[x][y]==mps[nd.f][nd.s]){
					q.push_front({x, y}); 
					level[x][y]=level[nd.f][nd.s];					
				}
				else{
					q.push_back({x, y}); 
					level[x][y]=level[nd.f][nd.s]+1;
				}
			}
		}
	}
	cout<<ans<<endl;
}

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