Submission #943477

#	Time	Username	Problem	Language	Result	Execution time	Memory
943477		NK_	Zoo (COCI19_zoo)	C++17	110 / 110	47 ms	10332 KiB

zoo

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define sz(x) int(x.size())

template<class T> using V = vector<T>;
using vi = V<int>;

const int INF = 1e9 + 10;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, M; cin >> N >> M;

	V<string> A(N); for(auto& x : A) cin >> x;

	V<vi> dst(N, vi(M, INF)), vis(N, vi(M, 0));


	dst[0][0] = 0; deque<array<int, 2>> q; q.push_back({0, 0});

	int ans = 0;
	while(sz(q)) {
		auto [r, c] = q.front(); q.pop_front();


		if (vis[r][c]) continue;
		vis[r][c] = 1;
		ans = max(ans, dst[r][c]);

		for(int dr = -1; dr <= 1; dr++) for(int dc = -1; dc <= 1; dc++) {
			if (abs(dr) + abs(dc) != 1) continue;

			int nr = r + dr, nc = c + dc;

			if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
			if (A[nr][nc] == '*') continue;

			if (A[nr][nc] != A[r][c]) {
				if (dst[nr][nc] > dst[r][c] + 1) {
					dst[nr][nc] = dst[r][c] + 1;
					q.push_back({nr, nc});
				}
			} else {
				if (dst[nr][nc] > dst[r][c]) {
					dst[nr][nc] = dst[r][c];
					q.push_front({nr, nc});
				}
			}
		}
	}

	cout << ans + 1 << nl;

	exit(0-0);
}

• Subtask 1: 45 / 45
• Subtask 2: 65 / 65