Submission #393545

#	Time	Username	Problem	Language	Result	Execution time	Memory
393545		Genius3435	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1029 ms	182728 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;


#define F first
#define S second
#define allv(v) v.begin(), v.end()
#define alla(a, N) a, a + N

inline void fastIO() {
	cin.tie(nullptr) -> sync_with_stdio(false);
}



const int dx[4] = { 0,  1,  0, -1};
const int dy[4] = { 1,  0, -1,  0};


const int arraysize = 5005;
char grid[arraysize][arraysize];
bool vis[arraysize][arraysize];
int dis[arraysize][arraysize];


inline string YNEOS(bool b) {
	return b ? "YES" : "NO";
}

inline string YNeos(bool b) {
	return b ? "Yes" : "No";
}



void solve() {
	int N, M; cin >> N >> M;
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < M; ++j)
			cin >> grid[i][j];
	
	int mx = 0;
	deque<pair<pii, int>> q;
	// {{i, j}, dis}
	q.emplace_front(pii{0, 0}, 1);
	dis[0][0] = 0, vis[0][0] = true;
	while (!q.empty()) {
		auto [p, d] = q.front();
		auto &[i, j] = p; q.pop_front();
		mx = max(mx, (dis[i][j] = d));

		for (int k = 0; k < 4; ++k) {
			int x = i + dx[k], y = j + dy[k];
			if (x < 0 || x >= N) continue;
			if (y < 0 || y >= M) continue;
			if (grid[x][y]=='.') continue;
			if (vis[x][y]==true) continue;

			vis[x][y] = true;
			if (grid[x][y] == grid[i][j])
				q.emplace_front(pii{x, y}, d);
			else q.emplace_back(pii{x, y}, d+1);
		}
	}

	cout << mx << '\n';
}



int main() {
	fastIO();
	solve();
}

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