Submission #975101

#	Time	Username	Problem	Language	Result	Execution time	Memory
975101		Adarsh	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	748 ms	338136 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define INF 10000
int mod = 1e9+7;
typedef pair<int, int> pii;
typedef pair<long, long> pll;


int n,m;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
string s[4040];

bool check(int x, int y){
    if(x<0 || x>=n || y<0 || y>=m || s[x][y]=='.'){
        return 0;
    }
    return 1;
}

void solve(){
   cin>>n>>m;
   for(int i=0;i<n;i++){
    cin>>s[i];
   }

   vector<vector<int>> dis;
   vector<vector<int>> vis;
   dis = vector<vector<int>>(n+1,vector<int>(m+1,1e18));
   vis = vector<vector<int>>(n+1,vector<int>(m+1,0));

   dis[0][0] = 1;
   deque<pair<int,int>> dq;
   dq.push_back({0,0});

   while(!dq.empty()){
     auto cur = dq.front();
     dq.pop_front();
    
     if(vis[cur.F][cur.S]){
        continue;
     }else{
        vis[cur.F][cur.S] = 1;
     }
     
     for(int i=0;i<4;i++){
        int nx = cur.F+dx[i];
        int ny = cur.S+dy[i];

        
        if(check(nx,ny)){
            int weight;
            if(s[nx][ny]==s[cur.F][cur.S]){
                weight = 0;
            }else{
                weight = 1;
            }

            if(dis[nx][ny]>dis[cur.F][cur.S]+weight){
                dis[nx][ny]=dis[cur.F][cur.S]+weight;
                if(weight){
                    dq.push_back({nx,ny});
                }else{
                    dq.push_front({nx,ny});
                }
            }
        }
     }

   }

   int ans = 1;

   for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        if(vis[i][j]){
            ans = max(ans,dis[i][j]);
        }
    }
   }
cout<<ans<<endl;
    
}


signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

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