Submission #1037007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037007		sssamui	Tracks in the Snow (BOI13_tracks)	C++17	2.19 / 100	177 ms	87376 KiB

tracks

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;

vector<int> radd = { -1, 0, 1, 0 };
vector<int> cadd = { -1, 0, 1, 0 };

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

	int h, w;
	cin >> h >> w;
	vector<vector<char>> trk(h + 2, vector<char>(w + 2, '.'));
	for (int i = 1; i <= h; i++) for (int j = 1; j <= w; j++) cin >> trk[i][j];

	priority_queue<pair<int, pair<int, int>>> bfs;
	int ans = 0;
	vector<vector<int>> dist(h + 2, vector<int>(w + 2, 0));
	if (trk[1][1] == '.') cout << 0;
	else
	{
		bfs.push({ -1, {1, 1} });
		while (!bfs.empty())
		{
			int nans = -bfs.top().first;
			int r = bfs.top().second.first;
			int c = bfs.top().second.second;
			bfs.pop();
			if (dist[r][c] == 0)
			{
				ans = nans;
				dist[r][c] = nans;
				for (int dir = 0; dir < 4; dir++)
				{
					if (trk[r + radd[dir]][c + cadd[dir]] == trk[r][c]) bfs.push({ -nans, {r + radd[dir], c + cadd[dir]} });
					else if (trk[r + radd[dir]][c + cadd[dir]] != '.') bfs.push({ -nans - 1, {r + radd[dir], c + cadd[dir]} });
				}
			}
		}

		cout << ans;
	}
}

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