제출 #1126651

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126651		Halym2007	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1363 ms	96524 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
#define dur exit(0)
#define dur1 return(0)
const int N = 4e3 + 5;
char a[N][N];
int n, m, vis[N][N];
queue <pii> q, q1;

int aa[] = {1, 0, -1, 0};
int bb[] = {0, 1, 0, -1};

void solve (char z) {
	while (!q.empty()) {
		int x = q.front().ff, y = q.front().ss;
		q.pop();
		if (vis[x][y]) continue;
		vis[x][y] = 1;
		for (int i = 0; i < 4; ++i) {
			int new_x = aa[i] + x, new_y = bb[i] + y;
			if (new_x < 1 or new_x > n or new_y > m or new_y < 1) continue;
			if (vis[new_x][new_y] or a[new_x][new_y] == '.') continue;
			
			if (a[new_x][new_y] != z) {
				q1.push({new_x, new_y});
			}
			else if (a[new_x][new_y] == z) {
				q.push({new_x, new_y});
			}
		}
	}
} 

int main () {
//	freopen ("input.txt", "r", stdin);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> m;
	int sana = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cin >> a[i][j];
			if (a[i][j] != '.') sana++;
		}
	}
	int cur = a[1][1];
	q.push({1, 1});
	for (int idx = 1; ; ++idx) {
		solve (cur);
		if (cur == 'F') cur = 'R';
		else cur = 'F';
		while (!q1.empty()) {
			q.push(q1.front());
			q1.pop();
		}
		if (q.empty()) return cout << idx, 0;
	}
//	cout << ayyr << " " << sana;
}


/*

TFFFT.....
T..F......
T..F......
T..F......
T..FFF....
TTTTTTTTTT

*/

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