Submission #378202

#	Time	Username	Problem	Language	Result	Execution time	Memory
378202		penguin133	Tracks in the Snow (BOI13_tracks)	C++14	47.40 / 100	2097 ms	81432 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
char g[4005][4005];
int ans[4005][4005];
int dx[] = {0,1,0,-1}, dy[] = {1, 0, -1, 0};
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int h,w,maxi = 0;
	cin >> h >> w;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			cin >> g[i][j];
		}
	}
	for(int i=1;i<=4000;i++)fill(ans[i] , ans[i] + 4005, 2e9  +5);
	queue<pair<int, int> >q;
	q.push(make_pair(1, 1));
	ans[1][1] = 0;
	while(!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		if(x == h && y == w)continue;
		for(int i=0;i<4;i++){
			int x1 = x + dx[i];
			int y1 = y + dy[i];
			if(g[x1][y1] == '.')continue;
			int ans1 = ans[x][y];
			if(g[x1][y1] != g[x][y])ans1++;
			if(ans[x1][y1] > ans1){
				ans[x1][y1] = ans1;
				q.push(make_pair(x1, y1));
			}
		}
	}
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			if(g[i][j] == '.')continue;
			maxi = max(maxi, ans[i][j]);
		}
	}
	cout << maxi + 1;
}

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