제출 #725284

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
725284		Radin_Zahedi2	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	761 ms	134780 KiB

tracks

#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)x.size()
//#define endl '\n'
const int mod = 1e9 + 7;
const int inf = 2e9 + 5;
const ll linf = 9e18 + 5;


int n, m;
const int N = 4e3 + 5;
char c[N][N];

int dist[N][N];

void init() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			c[i][j] = '.';
		}
	}
}

void input() {
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> c[i][j];
		}
	}
}

void bfs() {
	deque<pair<int, int>> dq;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			dist[i][j] = inf;
		}
	}


	dist[1][1] = 1;
	dq.push_back(mp(1, 1));

	while (!dq.empty()) {
		int x = dq.front().fi;
		int y = dq.front().se;
		dq.pop_front();

		for (int dx = -1; dx <= 1; dx++) {
			for (int dy = -1; dy <= 1; dy++) {
				if (abs(dx) + abs(dy) != 1) {
					continue;
				}

				if (dist[x + dx][y + dy] != inf) {
					continue;
				}

				if (c[x + dx][y + dy] == '.') {
					continue;
				}

				if (c[x + dx][y + dy] != c[x][y] && dist[x + dx][y + dy] > dist[x][y] + 1) {
					dist[x + dx][y + dy] = dist[x][y] + 1;
					dq.push_back(mp(x + dx, y + dy));
				}
				else if (dist[x + dx][y + dy] > dist[x][y]) {
					dist[x + dx][y + dy] = dist[x][y];
					dq.push_front(mp(x + dx, y + dy));
				}
			}
		}
	}
}

void solve() {
	bfs();

	int ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (dist[i][j] != inf) {
				ans = max(ans, dist[i][j]);
			}
		}
	}

	cout << ans;
}

void output() {
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int number_of_testcases = 1;
	//cin >> number_of_testcases;
	while (number_of_testcases--) {
		init();

		input();

		solve();

		output();
	}

	return 0;
}

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