Submission #768876

# Submission time Handle Problem Language Result Execution time Memory
768876 2023-06-28T19:54:37 Z 1ne Tracks in the Snow (BOI13_tracks) C++14
100 / 100
412 ms 77536 KB
/*
*  author : Apiram                  
*  created: 29.06.2023 01:16:40
*/

#include<bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n,m;cin>>n>>m;
	vector<int>dx = {-1,1,0,0};
	vector<int>dy = {0,0,-1,1};
	vector<string>arr(n);
	for (int i = 0;i<n;++i){
		cin>>arr[i];
	}
	deque<pair<int,int>>q;
	q.push_back({0,0});    
	vector<vector<bool>>visited(n,vector<bool>(m,0));
	visited[0][0] = 1;
	int ans = 1;
	char cur = arr[0][0];
	while(!q.empty()){
		auto u = q.back();
		q.pop_back();
		if (arr[u.first][u.second]!=cur){
			cur = arr[u.first][u.second];
			++ans;
		}
		for (int i = 0;i<4;++i){
			int nx = u.first + dx[i];
			int ny = u.second + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= m || arr[nx][ny] == '.' || visited[nx][ny])continue;
			visited[nx][ny] = true;
			if (arr[nx][ny] == arr[u.first][u.second]){
				q.push_back({nx,ny});
			}
			else{
				q.push_front({nx,ny});
			}
		}
	}
	cout<<ans<<'\n';		
	return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 8 ms 844 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 7 ms 852 KB Output is correct
16 Correct 8 ms 852 KB Output is correct
17 Correct 5 ms 808 KB Output is correct
18 Correct 4 ms 840 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 25 ms 3704 KB Output is correct
3 Correct 123 ms 35864 KB Output is correct
4 Correct 30 ms 8456 KB Output is correct
5 Correct 70 ms 20200 KB Output is correct
6 Correct 412 ms 49056 KB Output is correct
7 Correct 2 ms 672 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 25 ms 3688 KB Output is correct
14 Correct 15 ms 2364 KB Output is correct
15 Correct 8 ms 2556 KB Output is correct
16 Correct 13 ms 1760 KB Output is correct
17 Correct 61 ms 9292 KB Output is correct
18 Correct 31 ms 9096 KB Output is correct
19 Correct 30 ms 8556 KB Output is correct
20 Correct 29 ms 7780 KB Output is correct
21 Correct 77 ms 20852 KB Output is correct
22 Correct 67 ms 20172 KB Output is correct
23 Correct 118 ms 17404 KB Output is correct
24 Correct 68 ms 20360 KB Output is correct
25 Correct 181 ms 35824 KB Output is correct
26 Correct 304 ms 77536 KB Output is correct
27 Correct 355 ms 53484 KB Output is correct
28 Correct 408 ms 49108 KB Output is correct
29 Correct 400 ms 49508 KB Output is correct
30 Correct 376 ms 49792 KB Output is correct
31 Correct 323 ms 23380 KB Output is correct
32 Correct 302 ms 51384 KB Output is correct