Submission #867583

#	Time	Username	Problem	Language	Result	Execution time	Memory
867583		saarang123	Tracks in the Snow (BOI13_tracks)	C++17	45.10 / 100	2096 ms	195168 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

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

bool check(int nx, int ny){
	return (nx >= 0 && nx < n && ny >= 0 && ny < m);
}

struct item{
	int x, y, dist;
};

struct comp{
	bool operator()(item a, item b){
		return (a.dist < b.dist) || (a.dist == b.dist && make_pair(a.x, a.y) < make_pair(b.x, b.y));
	}
};

int bfs(vector<vector<char>>& grid){
	priority_queue<item, vector<item>, comp> q;
	q.push({0, 0, 1});
	vector<vector<int>> dist(n, vector<int>(m, 1e9));
	dist[0][0] = 1;
	while (!q.empty()){
		item i = q.top(); q.pop();
		if (dist[i.x][i.y] != i.dist) continue;
		for (int j = 0; j < 4; j++){
			int nx = i.x + dx[j], ny = i.y + dy[j];
			if (!check(nx, ny)) continue;
			if (grid[nx][ny] == '.') continue;
			int ndist = i.dist + (grid[nx][ny] != grid[i.x][i.y]);
			if (ndist < dist[nx][ny]){
				dist[nx][ny] = ndist;
				q.push({nx, ny, ndist});
			}
		}
	}

	//max distance
	int mx = 0;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			//cout << (dist[i][j] == 1e9 ? 0 : dist[i][j]) << ' ';
			if (grid[i][j] == '.') continue;
			if (dist[i][j] > mx){
				mx = dist[i][j];
			}
		}
		//cout << '\n';
	}
	return mx;
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	vector<vector<char>> grid(n, vector<char>(m));
	vector<int> cnt(2, 0); //r, f
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			cin >> grid[i][j];
			if (grid[i][j] == 'F') cnt[1]++;
			if (grid[i][j] == 'R') cnt[0]++;
		}
	}

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

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