제출 #592988

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
592988		beaboss	Tracks in the Snow (BOI13_tracks)	C++14	86.88 / 100	2101 ms	400656 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

int main() {
	int h, w;

	cin >> h >> w;

	vector<vector<char> > graph(h, vector<char>(w, 0));

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> graph[i][j];
		}
	}

	deque<vector<int> > bfs;

	bfs.push_back({0, 0});
	vector<vector<int> > dist(h, vector<int>(w, -1));
	dist[0][0] = 1;
	int ans = 0;
	vector<pair<int, int> > vec = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

	while (!bfs.empty()) {
		auto current = bfs.front();
		bfs.pop_front();
		ans = max(ans, dist[current[0]][current[1]]);
		// cout << current[0] << current[1] << dist[current[0]][current[1]] << endl;
		for (pair<int, int> val: vec) {
			int newx = current[0] + val.first;
			int newy = current[1] + val.second;
			if (newx >= 0 &&
				newx < h &&
				newy < w &&
				newy >= 0) {
				if (graph[newx][newy] == '.' || dist[newx][newy] != -1) continue;
				
				if (graph[newx][newy] == 
					graph[current[0]][current[1]]) {
					dist[newx][newy] = dist[current[0]][current[1]];
					bfs.push_front({newx, newy});
				} else {
					bfs.push_back({newx, newy});
					dist[newx][newy] = dist[current[0]][current[1]] + 1;
					
				}
			}
		}
	}

	cout << ans << endl;


}

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