Submission #1092453

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092453		keaucucal	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1132 ms	167168 KiB

tracks

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

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

int main() {
	int h, w;
	cin >> h >> w;
	vector<vector<int>> v(h, vector<int>(w, -1));
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			char c;
			cin >> c;
			switch (c) {
				case 'F':
					v[i][j] = 1;
					break;
				case 'R':
					v[i][j] = 0;
					break;
				default:
					v[i][j] = -1;
					break;
			}
		}
	}

	deque<pair<int, int>> dq;
	vector<vector<int>> dist(h, vector<int>(w));
	dist[0][0] = 1;
	dq.push_back({0, 0});

	int ans = 0;
	while (!dq.empty()) {
		int x = dq.front().first;
		int y = dq.front().second;
		dq.pop_front();

		ans = max(ans, dist[x][y]);

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i], ny = y + dy[i];
			if (nx < 0 || nx >= h || ny < 0 || ny >= w || dist[nx][ny] || v[nx][ny] == -1) continue;	

			if (v[x][y] == v[nx][ny]) {
				dist[nx][ny] = dist[x][y];
				dq.push_front({nx, ny});
			} else {
				dist[nx][ny] = dist[x][y] + 1;
				dq.push_back({nx, ny});
			}
		}
	}

	cout << ans << '\n';
	/*
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cout << dist[i][j] << ' ';
		}
		cout << endl;
	}
	*/
}

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