답안 #992099

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
992099 2024-06-03T22:51:08 Z vjudge1 Tracks in the Snow (BOI13_tracks) C++17
100 / 100
1108 ms 192392 KB
#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define pb push_back

typedef long long ll;
typedef pair<int,int> pii;



const int S = 4000;
char meadow[S][S];
int dist[S][S];
bool vis[S][S];
const int INF = 1e8;

void reset(){
	for(int i = 0; i < S; i++){
		for(int j = 0; j < S; j++){
			dist[i][j] = INF;
		}
	}
}
int solve(int h, int w){

	reset();
	int ans = 0;
	pii start = {0,0};
	deque<pii> dq;
	dq.push_back(start);
	dist[0][0] = 0;
	while(dq.size()){
		auto [a, b] = dq.front(); dq.pop_front();
		
		if(vis[a][b]) continue;
		vis[a][b] = true;
		char animal = meadow[a][b];
		// obtener vecinos
		vector<pii> vecinos;
		if (a > 0){
			if(!vis[a-1][b]){
				pii up = {a-1, b};
				char animal_up = meadow[up.ff][up.ss];
				if(animal_up != '.'){
					vecinos.pb(up);
				}
			}
		}
		if(a < h-1){
			if(!vis[a+1][b]){
				pii down = {a+1, b};
				char animal_down = meadow[down.ff][down.ss];
				if(animal_down != '.'){
					vecinos.pb(down);
				}
			}			
		}
		if(b > 0){
			if(!vis[a][b-1]){
				pii left = {a, b-1};
				char animal_left = meadow[left.ff][left.ss];
				if(animal_left != '.'){
					vecinos.pb(left);
				}
			}			
		}
		if(b < w-1){
			if(!vis[a][b+1]){
				pii right = {a, b+1};
				char animal_right = meadow[right.ff][right.ss];
				if(animal_right != '.'){
					vecinos.pb(right);
				}
			}
		}
		
		// iterar por vecinos
		for(auto [x,y]: vecinos){
			int d = 0;
			if(meadow[x][y] != animal){
				d = 1;
			}
			// if (dist[curr_node] + d > dist[to]) continue;
			if(dist[a][b] + d > dist[x][y]) continue;
			
			dist[x][y] = dist[a][b] + d;
			
			ans = max(ans, dist[x][y]);
			
			if(d == 1){
				dq.push_back({x,y});
			}
			else if(d == 0){
				dq.push_front({x,y});
			}
		}
		
	}
	return ans;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  int h, w; cin >> h >> w;
  
  for(int i = 0; i < h; i++){
	  for(int j = 0; j < w; j++){
		  char x; cin >> x;
		  meadow[i][j] = x;
	  }
  }
  cout << solve(h,w)+1;
  
  
	  
  
}
# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 67932 KB Output is correct
2 Correct 15 ms 66140 KB Output is correct
3 Correct 15 ms 66140 KB Output is correct
4 Correct 25 ms 68188 KB Output is correct
5 Correct 18 ms 67164 KB Output is correct
6 Correct 15 ms 66140 KB Output is correct
7 Correct 19 ms 66140 KB Output is correct
8 Correct 16 ms 66136 KB Output is correct
9 Correct 15 ms 66392 KB Output is correct
10 Correct 17 ms 66904 KB Output is correct
11 Correct 17 ms 66816 KB Output is correct
12 Correct 20 ms 67164 KB Output is correct
13 Correct 16 ms 67164 KB Output is correct
14 Correct 17 ms 67160 KB Output is correct
15 Correct 30 ms 70128 KB Output is correct
16 Correct 34 ms 67932 KB Output is correct
17 Correct 26 ms 67928 KB Output is correct
18 Correct 31 ms 68184 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 93448 KB Output is correct
2 Correct 73 ms 75088 KB Output is correct
3 Correct 308 ms 94288 KB Output is correct
4 Correct 89 ms 79564 KB Output is correct
5 Correct 216 ms 87892 KB Output is correct
6 Correct 1043 ms 119244 KB Output is correct
7 Correct 23 ms 94296 KB Output is correct
8 Correct 24 ms 93524 KB Output is correct
9 Correct 16 ms 66112 KB Output is correct
10 Correct 14 ms 66140 KB Output is correct
11 Correct 23 ms 94040 KB Output is correct
12 Correct 16 ms 66652 KB Output is correct
13 Correct 69 ms 75100 KB Output is correct
14 Correct 48 ms 71644 KB Output is correct
15 Correct 32 ms 72028 KB Output is correct
16 Correct 43 ms 67604 KB Output is correct
17 Correct 150 ms 79956 KB Output is correct
18 Correct 84 ms 80080 KB Output is correct
19 Correct 96 ms 79440 KB Output is correct
20 Correct 88 ms 79016 KB Output is correct
21 Correct 202 ms 88404 KB Output is correct
22 Correct 212 ms 87888 KB Output is correct
23 Correct 279 ms 84048 KB Output is correct
24 Correct 187 ms 90616 KB Output is correct
25 Correct 306 ms 94288 KB Output is correct
26 Correct 701 ms 192392 KB Output is correct
27 Correct 984 ms 120460 KB Output is correct
28 Correct 1058 ms 119108 KB Output is correct
29 Correct 1108 ms 115408 KB Output is correct
30 Correct 959 ms 123480 KB Output is correct
31 Correct 783 ms 91728 KB Output is correct
32 Correct 779 ms 124612 KB Output is correct