제출 #676603

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
676603		xyzxyz	Tracks in the Snow (BOI13_tracks)	C++14	97.81 / 100	1547 ms	110568 KiB

tracks

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

int main()
{
	int n, m;
	cin >> n >> m;
	vector<vector<char>> karte(n, vector<char>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> karte[i][j];
		}
	}
	vector<vector<int>> dist(n, vector<int>(m, 1e9));
	vector<pair<int, int>> richtungen = {{1,0}, {-1,0}, {0, 1}, {0, -1}};
	dist[0][0] = 1;
	deque<pair<int,int>> q;
	q.push_back({0, 0});
	int maxi = 0;
	while (!q.empty()) {
		pair<int,int> ort = q.front();
		q.pop_front();
		for (pair<int, int> richtung: richtungen) {
			if (ort.first+richtung.first>= 0 && ort.first+richtung.first < n && ort.second+richtung.second >= 0 && ort.second+richtung.second<m && karte[ort.first+richtung.first][ort.second+richtung.second]!='.') {
				if (karte[ort.first][ort.second] == karte[ort.first+richtung.first][ort.second+richtung.second] && dist[ort.first+richtung.first][ort.second+richtung.second]>dist[ort.first][ort.second]) {
					dist[ort.first+richtung.first][ort.second+richtung.second] = dist[ort.first][ort.second];
					q.push_front({ort.first+richtung.first, ort.second+richtung.second});
				} else if(dist[ort.first+richtung.first][ort.second+richtung.second]>dist[ort.first][ort.second]+1){
					dist[ort.first+richtung.first][ort.second+richtung.second] = dist[ort.first][ort.second]+1;
					maxi = max(maxi, dist[ort.first][ort.second]+1);
					q.push_back({ort.first+richtung.first, ort.second+richtung.second});
				}
			}
		}
	}
	cout << maxi;
	return 0;
}

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