제출 #1120613

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1120613		yazansh	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	657 ms	212696 KiB

tracks

/*
this code written by :
shimutski_zoro
*/
#include <bits/stdc++.h> 
 
using namespace std; 
 
#define yon(x) cout<<((x)?"YES\n":"NO\n"); 
#define all(x) x.begin(),x.end() 
#define rall(x) x.rbegin(),x.rend() 
#define ff first 
#define ss second 
#define em emplace 
#define emp emplace_back 
#define rep(i,j,k) for(int i=j;i<=k;i++) 
#define per(i,j,k) for(int i=k;i>=j;i--) 
#define forp(x,y,a) for(auto &[x,y]:(a)) 
typedef long long  ll; 
typedef pair<ll,ll> pll; 
typedef vector<ll> vl; 
typedef vector<pll> vpl; 
typedef vector<vl> vvl; 
typedef vector<vpl> vvpl; 
typedef vector<string> vs; 
typedef vector<set<ll> >vst;
typedef deque<ll> dl; 
const int mod=1e9+7;
const ll inf =1e18+1; 
const int N=1e6+1; 
const ll dx[]={1,0,-1,0},dy[]={0,1,0,-1}; 
void solve(){ 
    ll n,m;
    cin>>n>>m;
    vs g(n);
    rep(i,0,n-1){
        cin>>g[i];
    }             
    vvl d(n,vl(m));
    d[0][0]=1;
    deque<pll>dq;
    dq.emp(0,0);
    auto is=[&](ll x,ll y){
    return x>=0&&x<n&&y>=0&&y<m&&g[x][y]!='.';
    };
    ll ans=0;
    while(!dq.empty()){
ll x=dq.front().ff,y=dq.front().ss;
ans=max(ans,d[x][y]);
dq.pop_front();
rep(i,0,3){
    ll nx=x+dx[i],ny=y+dy[i];
    if(is(nx,ny)&&!d[nx][ny]){
        d[nx][ny]=d[x][y];
if(g[x][y]==g[nx][ny]){
    dq.push_front({nx,ny});

}else{
    d[nx][ny]++;
    dq.push_back({nx,ny});
}
    }
}
    }
    cout<<ans;                                                
}

signed main() { 

    ios_base::sync_with_stdio(NULL); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    #ifdef Usaco 
    string f="guard"; 
    freopen((f+".in").c_str(),"r",stdin); 
    freopen((f+".out").c_str(),"w",stdout); 
    #endif 
    int t = 1; 
    //cin >> t; 
    while (t--) { 
        solve();  
    } 
} 
/* 
example:

*/

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