Submission #952801

# Submission time Handle Problem Language Result Execution time Memory
952801 2024-03-24T21:23:59 Z 4QT0R Tracks in the Snow (BOI13_tracks) C++17
100 / 100
585 ms 183648 KB
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>

int pole[4004][4004];
int dist[4004][4004];
bool vis[4004][4004];
int k_x[4]={-1,0,1,0};
int k_y[4]={0,-1,0,1};

deque<pii> dq;

int bfs01(){
	int mx=0;
	dq.push_back({1,1});
	dist[1][1]=1;
	vis[1][1]=true;
	while(dq.size()){
		pii now=dq.front();
		dq.pop_front();
		mx=max(mx,dist[now.first][now.second]);
		for (int i = 0; i<4; i++){
			if (pole[now.first+k_x[i]][now.second+k_y[i]] && !vis[now.first+k_x[i]][now.second+k_y[i]]){
				if (pole[now.first+k_x[i]][now.second+k_y[i]]==pole[now.first][now.second]){
					dist[now.first+k_x[i]][now.second+k_y[i]]=dist[now.first][now.second];
					dq.push_front({now.first+k_x[i],now.second+k_y[i]});
				}
				else{
					dist[now.first+k_x[i]][now.second+k_y[i]]=dist[now.first][now.second]+1;
					dq.push_back({now.first+k_x[i],now.second+k_y[i]});
				}
				vis[now.first+k_x[i]][now.second+k_y[i]]=true;
			}
		}
	}
	return mx;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n,m;
	cin >> n >> m;
	char zn;
	for (int i = 1; i<=n; i++){
		for (int j = 1; j<=m; j++){
			cin >> zn;
			if (zn=='R')pole[i][j]=1;
			if (zn=='F')pole[i][j]=2;
		}
	}
	cout << bfs01() << '\n';
}
# Verdict Execution time Memory Grader output
1 Correct 13 ms 21340 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 11 ms 21156 KB Output is correct
5 Correct 4 ms 13916 KB Output is correct
6 Correct 2 ms 4556 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 1 ms 7004 KB Output is correct
10 Correct 4 ms 13660 KB Output is correct
11 Correct 3 ms 11612 KB Output is correct
12 Correct 6 ms 13916 KB Output is correct
13 Correct 5 ms 13912 KB Output is correct
14 Correct 4 ms 13912 KB Output is correct
15 Correct 12 ms 21168 KB Output is correct
16 Correct 14 ms 21236 KB Output is correct
17 Correct 11 ms 20828 KB Output is correct
18 Correct 8 ms 21084 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 35 ms 88908 KB Output is correct
2 Correct 48 ms 49756 KB Output is correct
3 Correct 273 ms 131176 KB Output is correct
4 Correct 84 ms 71688 KB Output is correct
5 Correct 175 ms 105300 KB Output is correct
6 Correct 585 ms 167540 KB Output is correct
7 Correct 21 ms 90972 KB Output is correct
8 Correct 19 ms 88924 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 19 ms 87128 KB Output is correct
12 Correct 2 ms 9052 KB Output is correct
13 Correct 45 ms 49756 KB Output is correct
14 Correct 27 ms 37724 KB Output is correct
15 Correct 28 ms 40020 KB Output is correct
16 Correct 20 ms 19036 KB Output is correct
17 Correct 113 ms 71424 KB Output is correct
18 Correct 101 ms 73800 KB Output is correct
19 Correct 92 ms 70996 KB Output is correct
20 Correct 67 ms 66772 KB Output is correct
21 Correct 169 ms 101976 KB Output is correct
22 Correct 174 ms 103400 KB Output is correct
23 Correct 238 ms 89492 KB Output is correct
24 Correct 167 ms 100432 KB Output is correct
25 Correct 538 ms 153688 KB Output is correct
26 Correct 298 ms 183648 KB Output is correct
27 Correct 421 ms 182404 KB Output is correct
28 Correct 556 ms 167372 KB Output is correct
29 Correct 558 ms 168164 KB Output is correct
30 Correct 503 ms 171280 KB Output is correct
31 Correct 450 ms 123912 KB Output is correct
32 Correct 395 ms 171224 KB Output is correct