제출 #730175

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
730175		a_aguilo	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	790 ms	123184 KiB

tracks

#include<bits/stdc++.h>

using namespace std;

int H, W;
vector<string> snow;
vector<vector<int>> distances;

int bfs(){
	deque<int> DQ;
	distances[0][0] = 1;
	int ans = 1;
	DQ.push_back(0);
	while(!DQ.empty()){
		int actual = DQ.front(); DQ.pop_front();
		int x = actual/W;
		int y = actual - W*x;
		ans = max(ans, distances[x][y]);
		if(x){
			if(distances[x-1][y] == -1){
				if(snow[x-1][y] == snow[x][y]){
					distances[x-1][y] = distances[x][y];
					DQ.push_front((x-1)*W + y);
				}
				else if (snow[x-1][y] != '.'){
					distances[x-1][y] = distances[x][y]+1;
					DQ.push_back((x-1)*W + y);
				}
			}
		}
		if(y){
			if(distances[x][y-1] == -1){
				if(snow[x][y-1] == snow[x][y]){
					distances[x][y-1] = distances[x][y];
					DQ.push_front((x)*W + y-1);
				}
				else if (snow[x][y-1] != '.'){
					distances[x][y-1] = distances[x][y]+1;
					DQ.push_back((x)*W + y-1);
				}
			}
		}
		if(x < (H-1)){
			if(distances[x+1][y] == -1){
				if(snow[x+1][y] == snow[x][y]){
					distances[x+1][y] = distances[x][y];
					DQ.push_front((x+1)*W + y);
				}
				else if (snow[x+1][y] != '.'){
					distances[x+1][y] = distances[x][y]+1;
					DQ.push_back((x+1)*W + y);
				}
			}
		}
		if(y < (W-1)){
			if(distances[x][y+1] == -1){
				if(snow[x][y+1] == snow[x][y]){
					distances[x][y+1] = distances[x][y];
					DQ.push_front((x)*W + y + 1);
				}
				else if (snow[x][y+1] != '.'){
					distances[x][y+1] = distances[x][y]+1;
					DQ.push_back((x)*W + y + 1);
				}
			}
		}
	}
	return ans;
}

int main(){
	cin >> H >> W;
	snow = vector<string>(H);
	for(int i = 0; i < H; ++i)cin >> snow[i];
	distances = vector<vector<int>>(H, vector<int>(W, -1));
	cout << bfs()<< endl;
	return 0;
}

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