oj.uz

Submission #542377

# Submission time Handle Problem Language Result Execution time Memory
542377 2022-03-26T09:56:22 Z Tam_theguide Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1597 ms 165212 KB 
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int dx[4]={0, 0, 1, -1};
const int dy[4]={1, -1, 0, 0};
char a[4005][4005];
bool visited[4005][4005];
int d[4005][4005];
int ans=1;
using P=pair<pair<int, int>, int>;
deque<P>dq;
bool check(int i, int j){
    if (a[i][j]!='.' && 1<=i && i<=n && 1<=j && j<=m) return true;
    else return false;
}
void bfs(){
    dq.push_back({{1, 1}, 0});
    d[1][1]=1;//vi ton 1 con vat;
    while (!dq.empty()){
        int distance=dq.front().second;
        int u=dq.front().first.first;
        int v=dq.front().first.second;
        dq.pop_front();
        if (visited[u][v]) continue;
        visited[u][v]=true;
        ans=max(ans, distance);
        for (int t=0; t<4; t++){
            int ii=u+dx[t];
            int jj=v+dy[t];
            if (check(ii, jj)==false || visited[ii][jj]) continue;
            if (a[u][v]!=a[ii][jj]){
                if (d[u][v]+1<d[ii][jj]){
                    d[ii][jj]=d[u][v]+1;
                    dq.push_back({{ii, jj}, d[ii][jj]});
                }
            }else{
                if (d[u][v]<d[ii][jj]){
                    d[ii][jj]=d[u][v];
                    dq.push_front({{ii, jj}, d[ii][jj]});
                }
            }
        }
    }
    cout<<ans;
}
int main(){
    cin>>n>>m;
    for (int i=1;i <=n; i++){
        for (int j=1; j<=m; j++){
            cin>>a[i][j];
            if (i==1 && j==1) d[i][j]=1;
            else d[i][j]=1e9;
        }
    }
    bfs();
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 7380 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 17 ms 7124 KB Output is correct
5 Correct 8 ms 4052 KB Output is correct
6 Correct 1 ms 568 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 2 ms 1468 KB Output is correct
10 Correct 7 ms 3528 KB Output is correct
11 Correct 6 ms 2928 KB Output is correct
12 Correct 12 ms 4180 KB Output is correct
13 Correct 9 ms 4156 KB Output is correct
14 Correct 8 ms 4052 KB Output is correct
15 Correct 27 ms 7432 KB Output is correct
16 Correct 33 ms 7256 KB Output is correct
17 Correct 24 ms 7116 KB Output is correct
18 Correct 19 ms 7124 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 45848 KB Output is correct
2 Correct 146 ms 22812 KB Output is correct
3 Correct 1111 ms 107744 KB Output is correct
4 Correct 266 ms 40940 KB Output is correct
5 Correct 661 ms 78900 KB Output is correct
6 Correct 1594 ms 127288 KB Output is correct
7 Correct 26 ms 47972 KB Output is correct
8 Correct 23 ms 45812 KB Output is correct
9 Correct 5 ms 704 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 23 ms 47044 KB Output is correct
12 Correct 3 ms 2128 KB Output is correct
13 Correct 141 ms 22732 KB Output is correct
14 Correct 81 ms 15436 KB Output is correct
15 Correct 79 ms 16928 KB Output is correct
16 Correct 59 ms 8184 KB Output is correct
17 Correct 341 ms 43928 KB Output is correct
18 Correct 316 ms 43464 KB Output is correct
19 Correct 272 ms 40864 KB Output is correct
20 Correct 236 ms 37884 KB Output is correct
21 Correct 655 ms 81360 KB Output is correct
22 Correct 658 ms 78896 KB Output is correct
23 Correct 667 ms 66832 KB Output is correct
24 Correct 621 ms 80768 KB Output is correct
25 Correct 1273 ms 107676 KB Output is correct
26 Correct 1416 ms 165212 KB Output is correct
27 Correct 1496 ms 134084 KB Output is correct
28 Correct 1593 ms 126776 KB Output is correct
29 Correct 1597 ms 123316 KB Output is correct
30 Correct 1560 ms 130300 KB Output is correct
31 Correct 1211 ms 83772 KB Output is correct
32 Correct 1521 ms 131684 KB Output is correct