Submission #952801

#	Time	Username	Problem	Language	Result	Execution time	Memory
952801		4QT0R	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	585 ms	183648 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>

int pole[4004][4004];
int dist[4004][4004];
bool vis[4004][4004];
int k_x[4]={-1,0,1,0};
int k_y[4]={0,-1,0,1};

deque<pii> dq;

int bfs01(){
	int mx=0;
	dq.push_back({1,1});
	dist[1][1]=1;
	vis[1][1]=true;
	while(dq.size()){
		pii now=dq.front();
		dq.pop_front();
		mx=max(mx,dist[now.first][now.second]);
		for (int i = 0; i<4; i++){
			if (pole[now.first+k_x[i]][now.second+k_y[i]] && !vis[now.first+k_x[i]][now.second+k_y[i]]){
				if (pole[now.first+k_x[i]][now.second+k_y[i]]==pole[now.first][now.second]){
					dist[now.first+k_x[i]][now.second+k_y[i]]=dist[now.first][now.second];
					dq.push_front({now.first+k_x[i],now.second+k_y[i]});
				}
				else{
					dist[now.first+k_x[i]][now.second+k_y[i]]=dist[now.first][now.second]+1;
					dq.push_back({now.first+k_x[i],now.second+k_y[i]});
				}
				vis[now.first+k_x[i]][now.second+k_y[i]]=true;
			}
		}
	}
	return mx;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n,m;
	cin >> n >> m;
	char zn;
	for (int i = 1; i<=n; i++){
		for (int j = 1; j<=m; j++){
			cin >> zn;
			if (zn=='R')pole[i][j]=1;
			if (zn=='F')pole[i][j]=2;
		}
	}
	cout << bfs01() << '\n';
}

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