Submission #379254

#	Time	Username	Problem	Language	Result	Execution time	Memory
379254		mariowong	Tracks in the Snow (BOI13_tracks)	C++14	10.94 / 100	2091 ms	124444 KiB

tracks

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

struct dir{
	int vt,hz;
}a[8]={{0,1},{0,-1},{1,0},{1,-0}};

int h,w,ct,mv,ans,dis[4005][4005],len,x,y,newx,newy;
char s[4005][4005],c;
bool vis[4005][4005];
priority_queue <pair<int,pair<pair<int,int>,char>  >  > q; 
int main(){
	ios::sync_with_stdio(false);
	cin >> h >> w;
	for (int i=1;i<=h;i++){
		for (int j=1;j<=w;j++){
			cin >> s[i][j];
			if (s[i][j] != '.')
			ct++;
		}
	}
	q.push(make_pair(-1,make_pair(make_pair(1,1),s[1][1])));
	while (!q.empty()){
		x=q.top().second.first.first; y=q.top().second.first.second;
		len=-q.top().first; c=q.top().second.second; 
		q.pop();
		if (!vis[x][y]){
			vis[x][y]=true; dis[x][y]=len;
			for (int i=0;i<4;i++){
				newx=x+a[i].vt; newy=y+a[i].hz;
				if (newx > 0 && newx <= h && newy > 0 && newy <= w && !vis[newx][newy] && s[newx][newy] != '.'){
					if (c != s[newx][newy])
					q.push(make_pair(-len-1,make_pair(make_pair(newx,newy),s[newx][newy])));
					else
					q.push(make_pair(-len,make_pair(make_pair(newx,newy),s[newx][newy])));
				}
			}
		}
	}
	for (int i=1;i<=h;i++){
		for (int j=1;j<=w;j++){
			ans=max(ans,dis[i][j]);
		}
	}
	cout << ans << "\n";
	return 0;
}	

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