Submission #1043186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043186		ezGeometry	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	979 ms	110624 KiB

tracks

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>

using namespace std;

int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };

int main() {
	int n, m;
	cin >> n >> m;

	vector<vector<char>> grid(n + 2, vector<char>(m + 2, '.'));

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

	vector<vector<int>> bfs(n + 2, vector<int>(m + 2, 1e9));
	bfs[1][1] = 1;

	deque<pair<int, int>> cur;
	cur.push_back(make_pair(1, 1));

	while (cur.size()) {
		auto c = cur.front();
		cur.pop_front();

		for (int i = 0; i < 4; i++) {
			int nx = c.first + dx[i];
			int ny = c.second + dy[i];

			int w = 1;
			if (grid[nx][ny] == grid[c.first][c.second]) {
				w = 0;
			}
			if (grid[nx][ny] == '.') {
				w = 1e9;
			}

			if (w != 1e9) {
				if (bfs[nx][ny] > bfs[c.first][c.second] + w) {
					bfs[nx][ny] = bfs[c.first][c.second] + w;
					if (w == 1) {
						cur.push_back(make_pair(nx, ny));
					}
					else {
						cur.push_front(make_pair(nx, ny));
					}
				}
			}
		}
	}

	int ans = 1;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (grid[i][j] != '.') {
				ans = max(ans, bfs[i][j]);
			}
		}
	}

	cout << ans << endl;
}

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