Submission #876655

#	Time	Username	Problem	Language	Result	Execution time	Memory
876655		vjudge1	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	568 ms	90960 KiB

tracks

#include <iostream>
#include <vector>
#include <queue>

#define endl '\n'
#define pb emplace_back
#define front back
#define pop pop_back
#define push emplace_back
#define fr first
#define sc second
#define mp make_pair

using namespace std;

typedef pair<int, int> pi;

int n, h, w;
const int MAXN = 4010;

string mat[4010];

vector<pi> q[2];

bool used[MAXN][MAXN];


int x[4] = {1, 0, -1, 0};
int y[4] = {0, -1, 0, 1};

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

	cin >> h >> w;

	for(int i=0; i<h; i++) cin >> mat[i];

	int p, cnt = 0;
	used[0][0] = 1;

	p = (mat[0][0] == 'F');	

	q[p].pb(mp(0, 0));
	while(!q[0].empty() || !q[1].empty()){
		
		while(!q[p].empty()){
			pi v = q[p].front();
			q[p].pop();

			
			for(int i=0; i<4; i++){
				
				pi u = mp(v.fr+x[i], v.sc+y[i]);

				
				if(u.fr == -1 || u.sc == -1 || u.fr == h || u.sc == w || mat[u.fr][u.sc] == '.') continue;

				if(used[u.fr][u.sc]) continue;

				bool tp = (mat[u.fr][u.sc] == 'F');
				q[tp].push(u);
				used[u.fr][u.sc] = 1;
			
			}
		}

		p ^= 1;
		cnt++;
	}

	cout << cnt << endl;

	return 0;

}

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