제출 #444927

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
444927		aryan12	Tracks in the Snow (BOI13_tracks)	C++17	0 / 100	931 ms	216956 KiB

tracks

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

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

int n, m;
vector<string> a;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

void Solve() {
	cin >> n >> m;
	for(int i = 0; i < n; i++) {
		string s;
		cin >> s;
		a.push_back(s);
	}
	int dist[n][m];
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			dist[i][j] = INT_MAX;
		}
	}
	dist[0][0] = 1;
	deque<array<int, 2> > dq;
	dq.push_back({0, 0});
	int ans = INT_MAX;
	while(!dq.empty()) {
		int curx = dq[0][0], cury = dq[0][1];
		dq.pop_front();
		for(int i = 0; i < 4; i++) {
			int x = curx + dx[i], y = cury + dy[i];
			if(x < 0 || x >= n || y < 0 || y >= m || a[x][y] == '.') {
				continue;
			}
			if(a[x][y] == a[curx][cury] && dist[x][y] > dist[curx][cury]) {
				dist[x][y] = dist[curx][cury];
				dq.push_front({x, y});
			}
			if(a[x][y] != a[curx][cury] && dist[x][y] > dist[curx][cury] + 1) {
				dist[x][y] = dist[curx][cury] + 1;
				dq.push_back({x, y});
				ans = min(ans, dist[x][y]);
			}
		}
	}
	cout << ans << "\n";
}

int32_t main() {
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	///cin >> t;
	while(t--) {
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

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