Submission #575750

#	Time	Username	Problem	Language	Result	Execution time	Memory
575750		acatmeowmeow	Tracks in the Snow (BOI13_tracks)	C++11	2.19 / 100	923 ms	277236 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

#define int long long 

const int N = 4e3 + 5;
int n, m, d[N][N], rab = 0, fox = 0;
char grid[N][N];
vector<int> dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
deque<pair<int, pair<int, int>>> dq;

bool inbound(int x, int y) {
	return x >= 1 && x <= n && y >= 1 && y <= m && grid[x][y] != '.';
}

void bfs() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			d[i][j] = 1e18;
		}
	}
	dq.push_front({1, {1, 1}});
	d[1][1] = 1;
	while (dq.size()) {
		int p = dq.front().first, x = dq.front().second.first, y = dq.front().second.second; dq.pop_front();
		if (p != d[x][y]) continue;
		for (int k = 0; k < 4; k++) {
			int tox = x + dx[k], toy = y + dy[k];
			if (!inbound(tox, toy)) continue;
			int c = grid[x][y] != grid[tox][toy];
			if (d[tox][toy] <= d[x][y] + c) continue;
			d[tox][toy] = d[x][y] + c;
			if (c) dq.push_back({d[tox][toy], {tox, toy}});
			else dq.push_front({d[tox][toy], {tox, toy}});
		}
	}
	cout << max(d[n][m], rab + fox) << '\n';
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> grid[i][j];
			if (grid[i][j] == 'R') rab = 1;
			if (grid[i][j] == 'F') fox = 1;
		}
	}
	bfs();
	return 0;
}

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