제출 #1042097

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

tracks

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
void fastIO() {ios_base::sync_with_stdio(false), cin.tie(nullptr);}

const int INF = 1e9;
const int MAXR = 4001;
const int MAXC = 4001;
const int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};

int R, C;
char grid[MAXR][MAXC];

int dist[MAXR][MAXC];
int ans = 0;

signed main() {
	fastIO();

	cin >> R >> C;
	char on;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			cin >> on;
			grid[r][c] = on;
		}
	}

	if (grid[0][0] == '.') {
		cout << "0\n";
		return 0;
	}

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			dist[r][c] = INF;
		}
	}
	dist[0][0] = 1;

	deque<pair<int, int>> DQ;
	DQ.push_back({0, 0});

	pair<int, int> p;
	int r, c;
	while (!DQ.empty()) {
		p = DQ.front();
		r = p.f, c = p.s;
		DQ.pop_front();

		for (int i = 0; i < 4; i++) {
			if (0 > r + dr[i] || r + dr[i] >= R || 0 > c + dc[i] || c + dc[i] >= C) continue;
			if (grid[r + dr[i]][c + dc[i]] == '.') continue;

			if (grid[r + dr[i]][c + dc[i]] == grid[r][c] && dist[r + dr[i]][c + dc[i]] > dist[r][c]) {
				dist[r + dr[i]][c + dc[i]] = dist[r][c];
				DQ.push_front({r + dr[i], c + dc[i]});
			}
			else if (dist[r + dr[i]][c + dc[i]] > dist[r][c] + 1) {
				dist[r + dr[i]][c + dc[i]] = dist[r][c] + 1;
				DQ.push_back({r + dr[i], c + dc[i]});
			}

			ans = max(ans, dist[r + dr[i]][c + dc[i]]);
		}
	}

	cout << ans << "\n";
}

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