제출 #1091499

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1091499		ef10	Tracks in the Snow (BOI13_tracks)	C++17	51.15 / 100	632 ms	90368 KiB

tracks

// Source: https://usaco.guide/general/io

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

int H, W;
string M[4005];
bool v[4005][4005];

int main() {
	cin >> H >> W;
	for (int i = 0; i < H; i++) {
		cin >> M[i];
	}
	if (M[0][0] == '.') return 0;
	deque<pair<int,int> > q;
	q.push_back(make_pair(0,0));
	v[0][0] = true;
	int res = 1;
	char current = M[0][0];
	while (!q.empty()) {
		auto c = q.front();
		q.pop_front();
		if (M[c.first][c.second] != current) {
			res++;
			current = M[c.first][c.second];
		}
		for (auto i : {-1,1}) {
			for (auto j : {0,1}) {
				if (j==0) {
					if (((i < 0 && c.first > 0) || (i > 0 && c.first < W-1)) && !v[c.first+i][c.second] && M[c.first+i][c.second] != '.') {
						v[c.first+i][c.second] = true;
						if (M[c.first][c.second] == M[c.first+i][c.second]) {
							q.push_front(make_pair(c.first+i,c.second));
						} else {
							q.push_back(make_pair(c.first+i,c.second));
						}
					}
				} else {
					if (((i < 0 && c.second > 0) || (i > 0 && c.second < H-1)) && !v[c.first][c.second+i] && M[c.first][c.second+i] != '.') {
						v[c.first][c.second+i] = true;
						if (M[c.first][c.second] == M[c.first][c.second+i]) {
							q.push_front(make_pair(c.first,c.second+i));
						} else {
							q.push_back(make_pair(c.first,c.second+i));
						}
					}
				}
			}
		}
	}
	cout << res << endl;
}

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