Submission #541406

#	Time	Username	Problem	Language	Result	Execution time	Memory
541406		Nirey	Tracks in the Snow (BOI13_tracks)	C++17	22.19 / 100	41 ms	8396 KiB

tracks

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

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

int n,m,depth[400][400],ans=1;
string snow[400];

bool inside(int x,int y){
	return (x>-1 && x<n && y>-1 && y<m && snow[x][y]!='.');
}

int main(){
	cin >>n >>m;
	for(int i=0;i<n;i++) cin >>snow[i];
	deque<pair<int,int>> q;
	q.push_back({0,0});
	depth[0][0]=1;
	while(q.size()){
	 pair<int,int> c=q.front();
	 q.pop_front();
	 ans=max(ans,depth[c.first][c.second]);
	 
	for(int i=0;i<4;i++){
	int x=c.first+dx[i],y=c.second+dy[i];
	if(inside(x,y) && not depth[x][y]){
	 if(snow[x][y]==snow[c.first][c.second]){
	 depth[x][y]=depth[c.first][c.second];
	  q.push_front({x,y});
	 }
	 else {
	  depth[x][y]=depth[c.first][c.second]+1;
	  q.push_back({x,y});
	 }
	}
	}
	}
	cout << ans << endl;

	return 0;
}

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