제출 #1272913

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272913		ayhamzaidd	Tracks in the Snow (BOI13_tracks)	C++20	89.06 / 100	2102 ms	191040 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define pi pair<ll,pii>
#define fi first
#define se second

const ll N=2e3+5,MOD=1e9+7,INF=1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
   
    
    int n,m;
    cin>>n>>m;
    char c[n+5][m+5];
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin>>c[i][j];
        }
    }

    vector<vector<ll>> d(n+5, vector<ll>(m+5, -1));
    priority_queue<pi,vector<pi>,greater<pi>> pq;
    pq.push({1,{1,1}});
    d[1][1]=1;

    int dx[]={0,0,1,-1};
    int dy[]={1,-1,0,0};

    ll ans=0;
    while(!pq.empty()){
        pi cur=pq.top();
        int x=cur.se.fi,y=cur.se.se;
        pq.pop();
        ans=max(ans,cur.fi);
        for(int i=0; i<4; i++){
            int nx=dx[i]+x;
            int ny=dy[i]+y;

            if(nx<1 || nx>n || ny<1 || ny>m)continue;
            if(d[nx][ny]!=-1)continue;
            if(c[nx][ny]=='.')continue;
            if(c[nx][ny]==c[x][y]){
                pq.push({cur.fi,{nx,ny}});
                d[nx][ny]=cur.fi;
            }
            else{
                pq.push({cur.fi+1,{nx,ny}});
                d[nx][ny]=cur.fi+1;
            }
        }
    }
    cout<<ans;
}

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