Submission #1108090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108090		0pt1mus23	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	577 ms	230140 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 4e3 +5, inf = INT_MAX, LL = 30;
 
int depth[sze][sze];
char arr[sze][sze];
const int dx[4] = {-1,1,0,0};
const int dy[4] = {0,0,-1,1};
int n,m;
void rush(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            depth[i][j]=inf;
            cin>>arr[i][j];
        }
    }
    
    deque<pair<int,int>> q;
    q.push_back({0,0});
    depth[0][0]=1;
    int ans=1;

    while(!q.empty()){
        pair<int,int> node = q.front();
        q.pop_front();
        ans=max(ans,depth[node.first][node.second]);
        for(int i=0;i<4;i++){
            int x=node.first + dx[i];
            int y=node.second + dy[i];
            if(min(x,y)>=0 && x<n && y<m && arr[x][y]!='.'){
                if(depth[x][y] >( depth[node.first][node.second] + (arr[node.first][node.second]!=arr[x][y]) )){
                    depth[x][y] = ( depth[node.first][node.second] + (arr[node.first][node.second]!=arr[x][y]) );

                    if(arr[x][y]==arr[node.first][node.second]){
                        q.push_front({x,y});
                    }
                    else{
                        q.push_back({x,y});
                    }
                }
            }
        }
    }

    putr(ans);
}
 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int tt = 1; 
    // cin>>tt;
 
    while(tt--){
        rush();
    }
 
    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70