제출 #876628

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
876628		vjudge1	Tracks in the Snow (BOI13_tracks)	C++17	86.88 / 100	2113 ms	939532 KiB

tracks

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

#define endl '\n'
#define pb push_back

using namespace std;

int n, h, w;
const int MAXN = 16e6 + 1000;

string mat[4010];

queue<int> q[2];
vector<int> adj[MAXN];

bool tp[MAXN], used[MAXN];



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

	cin >> h >> w;

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


	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			if(mat[i][j] == '.') continue;

			int v = (i*w) + j;
			int u = (i+1)*w + j;

			if(i < (h-1) && mat[i+1][j] != '.'){
				adj[v].pb(u);
				adj[u].pb(v);
			}

			u = (i*w) + j + 1;
			if(j < (w-1) && mat[i][j+1] != '.'){
				adj[v].pb(u);
				adj[u].pb(v);
			}

			if(mat[i][j] == 'F') tp[v] = 0;
			else tp[v] = 1;
		}
	}



	int p, cnt=0;	
	if(mat[0][0] == 'F'){
		q[0].emplace(0);
		p = 0;
	}
	else{
		q[1].emplace(0);
		p = 1;
	}

	used[0] = 1;

	while(!q[0].empty() || !q[1].empty()){
		
		while(!q[p].empty()){
			int v = q[p].front();

			q[p].pop();
			
			for(int u : adj[v]){
				if(used[u]) continue;

				q[tp[u]].emplace(u);
				used[u] = 1;
			}
		}

		p ^= 1;
		cnt++;
	}

	cout << cnt << endl;

	return 0;

}

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