제출 #1037010

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1037010		sssamui	Tracks in the Snow (BOI13_tracks)	C++17	2.19 / 100	232 ms	78992 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));
	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