Submission #716990

# Submission time Handle Problem Language Result Execution time Memory
716990 2023-03-31T17:20:57 Z study Tracks in the Snow (BOI13_tracks) C++17
100 / 100
468 ms 101632 KB
#include <bits/stdc++.h>
using namespace std;

const int N = 4000;

string grid[N];
bool vu[N][N];
int h,w;

vector<pair<int,int>> dir = {{1,0},{0,1},{-1,0},{0,-1}};

struct node{
	int x,y,val;
};

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> h >> w;
	for (int i=0; i<h; ++i){
		cin >> grid[i];
	}
	deque<node> q;
	q.emplace_back(node{0,0,1});
	int ans = 0;
	while (!q.empty()){
		auto f = q.front();
		q.pop_front();
		ans = max(ans,f.val);
		for (auto i:dir){
			int nx = i.first+f.x, ny = i.second+f.y;
			if (nx >= 0 and ny >= 0 and nx < h and ny < w and !vu[nx][ny] and grid[nx][ny] != '.'){
				vu[nx][ny] = true;
				if (grid[f.x][f.y] != grid[nx][ny]) q.emplace_back(node{nx,ny,f.val+1});
				else q.emplace_front(node{nx,ny,f.val});
			}
		}
	}
	cout << ans;
	return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 9 ms 2724 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 5 ms 2772 KB Output is correct
5 Correct 2 ms 1620 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 2 ms 1492 KB Output is correct
11 Correct 3 ms 1364 KB Output is correct
12 Correct 5 ms 1720 KB Output is correct
13 Correct 3 ms 1620 KB Output is correct
14 Correct 2 ms 1620 KB Output is correct
15 Correct 8 ms 2644 KB Output is correct
16 Correct 12 ms 2644 KB Output is correct
17 Correct 7 ms 2516 KB Output is correct
18 Correct 5 ms 2772 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 9 ms 15336 KB Output is correct
2 Correct 29 ms 6996 KB Output is correct
3 Correct 144 ms 33756 KB Output is correct
4 Correct 38 ms 11756 KB Output is correct
5 Correct 125 ms 21864 KB Output is correct
6 Correct 443 ms 54592 KB Output is correct
7 Correct 10 ms 16084 KB Output is correct
8 Correct 11 ms 15316 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 13 ms 15772 KB Output is correct
12 Correct 1 ms 980 KB Output is correct
13 Correct 30 ms 7016 KB Output is correct
14 Correct 18 ms 4992 KB Output is correct
15 Correct 13 ms 5332 KB Output is correct
16 Correct 15 ms 2736 KB Output is correct
17 Correct 74 ms 12632 KB Output is correct
18 Correct 49 ms 12504 KB Output is correct
19 Correct 45 ms 11676 KB Output is correct
20 Correct 39 ms 10928 KB Output is correct
21 Correct 92 ms 22620 KB Output is correct
22 Correct 118 ms 21836 KB Output is correct
23 Correct 150 ms 18660 KB Output is correct
24 Correct 102 ms 22396 KB Output is correct
25 Correct 229 ms 33760 KB Output is correct
26 Correct 300 ms 101632 KB Output is correct
27 Correct 371 ms 84948 KB Output is correct
28 Correct 468 ms 54708 KB Output is correct
29 Correct 423 ms 50840 KB Output is correct
30 Correct 403 ms 61584 KB Output is correct
31 Correct 359 ms 24676 KB Output is correct
32 Correct 332 ms 69740 KB Output is correct