Submission #378204

#	Time	Username	Problem	Language	Result	Execution time	Memory
378204		penguin133	Tracks in the Snow (BOI13_tracks)	C++14	71.56 / 100	2101 ms	142380 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define int long long
char g[4005][4005];
int ans[4005][4005];
int dx[] = {0,1,0,-1}, dy[] = {1, 0, -1, 0};
inline int ReadInt() {
    int x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9'){
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
    return x;
}
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(x1 < 1 || x1 > h || y1 < 1 ||y1 > w)continue;
			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;
}

Compilation message (stderr)

tracks.cpp:17:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   17 | main(){
      |      ^

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