제출 #333971

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
333971		codemaster111	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	954 ms	130812 KiB

tracks

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

const int MX = 4001;
int n, m, d[MX][MX], dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
string g[MX];

bool inside(int r, int c) {
	return (r >= 0 && r < n && c >= 0 && c < m && g[r][c] != '.');
}

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < n; ++i) cin >> g[i];

	int ans = 1;
	d[0][0] = 1;
	deque<pair<int, int>> q;
	q.push_front({0, 0});
	while (!q.empty()) {
		pair<int, int> v = q.front(); q.pop_front();
		ans = max(ans, d[v.first][v.second]);
		for (int i = 0; i < 4; ++i) {
			int x = v.first+dx[i], y = v.second+dy[i];
			if (inside(x, y) && d[x][y] == 0) {
				if (g[x][y] == g[v.first][v.second]) {
					d[x][y] = d[v.first][v.second];
					q.push_front({x, y});
				} else {
					d[x][y] = d[v.first][v.second]+1;
					q.push_back({x, y});
				}
			}
		}
	}
	cout << ans << '\n';
}

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