oj.uz

Submission #153755

# Submission time Handle Problem Language Result Execution time Memory
153755 2019-09-15T19:44:10 Z brcode Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1733 ms 129660 KB 
#include <iostream>
#include <queue>
using namespace std;
int n,m;
const int MAXN = 4010;
int dx[5] = {1,0,-1,0};
int dy[5] = {0,1,0,-1};
string arr[MAXN];
int dp[MAXN][MAXN];
int ans;
bool check(int x,int y){
    if(x>0 && x<=n && y>0 && y<=m && arr[x][y]!='.'){
        return true;
    }
    return false;
}
 deque<pair<int,int>> q1;
int main(){

    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        arr[i] = '.'+arr[i];
        //cout<<arr[i]<<endl;
    }
   
    dp[1][1] = 1;
  
    q1.push_front(make_pair(1,1));
   
    while(!q1.empty()){
        
        auto curr = q1.front();
        q1.pop_front();
       
        ans = max(ans,dp[curr.first][curr.second]);
        for(int i=0;i<4;i++){
            int x = curr.first+dx[i];
            int y = curr.second+dy[i];
            if(check(x,y) && dp[x][y]==0){
                if(arr[x][y] == arr[curr.first][curr.second]){
                    q1.push_front(make_pair(x,y));
                    dp[x][y] = dp[curr.first][curr.second];
                }else{
                    q1.push_back(make_pair(x,y));
                    dp[x][y] = dp[curr.first][curr.second]+1;
                    
                }
            }
        }
    }
    cout<<ans<<endl;
    
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3832 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 21 ms 3576 KB Output is correct
5 Correct 10 ms 2040 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 3 ms 760 KB Output is correct
9 Correct 3 ms 888 KB Output is correct
10 Correct 9 ms 1656 KB Output is correct
11 Correct 7 ms 1588 KB Output is correct
12 Correct 13 ms 2168 KB Output is correct
13 Correct 10 ms 2040 KB Output is correct
14 Correct 10 ms 2040 KB Output is correct
15 Correct 30 ms 3704 KB Output is correct
16 Correct 31 ms 3832 KB Output is correct
17 Correct 27 ms 3704 KB Output is correct
18 Correct 20 ms 3580 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 15992 KB Output is correct
2 Correct 139 ms 11808 KB Output is correct
3 Correct 1142 ms 73640 KB Output is correct
4 Correct 315 ms 29196 KB Output is correct
5 Correct 672 ms 50640 KB Output is correct
6 Correct 1729 ms 108616 KB Output is correct
7 Correct 25 ms 16632 KB Output is correct
8 Correct 25 ms 15992 KB Output is correct
9 Correct 7 ms 760 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 25 ms 16376 KB Output is correct
12 Correct 5 ms 1144 KB Output is correct
13 Correct 138 ms 11768 KB Output is correct
14 Correct 81 ms 7924 KB Output is correct
15 Correct 84 ms 10332 KB Output is correct
16 Correct 61 ms 4856 KB Output is correct
17 Correct 357 ms 25296 KB Output is correct
18 Correct 332 ms 32032 KB Output is correct
19 Correct 297 ms 29116 KB Output is correct
20 Correct 258 ms 22396 KB Output is correct
21 Correct 675 ms 49828 KB Output is correct
22 Correct 674 ms 50808 KB Output is correct
23 Correct 676 ms 41548 KB Output is correct
24 Correct 674 ms 46920 KB Output is correct
25 Correct 1361 ms 94684 KB Output is correct
26 Correct 1215 ms 129660 KB Output is correct
27 Correct 1663 ms 129240 KB Output is correct
28 Correct 1733 ms 108596 KB Output is correct
29 Correct 1716 ms 106240 KB Output is correct
30 Correct 1641 ms 112084 KB Output is correct
31 Correct 1173 ms 71368 KB Output is correct
32 Correct 1517 ms 115896 KB Output is correct