답안 #989878

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
989878 2024-05-28T22:58:13 Z vjudge1 Tracks in the Snow (BOI13_tracks) C++17
70.9375 / 100
966 ms 227104 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 < h-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 Incorrect 30 ms 67932 KB Output isn't correct
2 Correct 11 ms 66140 KB Output is correct
3 Correct 12 ms 66140 KB Output is correct
4 Correct 26 ms 68956 KB Output is correct
5 Correct 14 ms 67164 KB Output is correct
6 Correct 11 ms 66136 KB Output is correct
7 Correct 11 ms 66140 KB Output is correct
8 Incorrect 11 ms 66140 KB Output isn't correct
9 Correct 12 ms 66396 KB Output is correct
10 Correct 13 ms 66908 KB Output is correct
11 Correct 14 ms 66904 KB Output is correct
12 Correct 16 ms 67284 KB Output is correct
13 Correct 13 ms 67164 KB Output is correct
14 Correct 14 ms 67164 KB Output is correct
15 Correct 25 ms 69980 KB Output is correct
16 Incorrect 33 ms 68188 KB Output isn't correct
17 Correct 21 ms 67980 KB Output is correct
18 Correct 26 ms 69012 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 633 ms 214868 KB Output isn't correct
2 Correct 64 ms 75060 KB Output is correct
3 Correct 278 ms 94164 KB Output is correct
4 Incorrect 80 ms 79444 KB Output isn't correct
5 Correct 196 ms 87892 KB Output is correct
6 Correct 937 ms 119368 KB Output is correct
7 Correct 666 ms 227104 KB Output is correct
8 Incorrect 624 ms 213072 KB Output isn't correct
9 Incorrect 11 ms 65884 KB Output isn't correct
10 Incorrect 12 ms 65884 KB Output isn't correct
11 Correct 708 ms 219712 KB Output is correct
12 Correct 12 ms 66648 KB Output is correct
13 Correct 60 ms 74964 KB Output is correct
14 Incorrect 40 ms 71508 KB Output isn't correct
15 Correct 32 ms 72016 KB Output is correct
16 Incorrect 16 ms 66396 KB Output isn't correct
17 Correct 133 ms 80088 KB Output is correct
18 Correct 74 ms 79956 KB Output is correct
19 Incorrect 77 ms 79440 KB Output isn't correct
20 Incorrect 38 ms 72276 KB Output isn't correct
21 Correct 211 ms 91096 KB Output is correct
22 Correct 172 ms 88144 KB Output is correct
23 Incorrect 205 ms 82256 KB Output isn't correct
24 Correct 196 ms 95696 KB Output is correct
25 Correct 255 ms 94288 KB Output is correct
26 Correct 652 ms 192972 KB Output is correct
27 Correct 815 ms 120444 KB Output is correct
28 Correct 966 ms 119212 KB Output is correct
29 Correct 943 ms 115672 KB Output is correct
30 Correct 840 ms 123368 KB Output is correct
31 Incorrect 716 ms 91812 KB Output isn't correct
32 Correct 702 ms 124608 KB Output is correct