제출 #1302684

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1302684		inifnite	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	554 ms	173024 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pii pair<int,int>

const int dir[4][2]= {{0,-1}, {-1,0}, {0,1}, {1,0}};

void solve() {
    int n,m; cin>>n>>m;
    string str[n];
    for(int i=0; i<n; i++) cin>>str[i];
    
    int vis[n][m]; memset(vis,0,sizeof(vis));
    int ans=0;
    
    deque<pii> dq;
    dq.push_back({0,0});
    pii tp;
    vis[0][0]=1;
    
    int dp[n][m]; memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    
    while(dq.size()) {
        tp=dq.front(); dq.pop_front();
        ans=dp[tp.f][tp.s];
        for(int i=0; i<4; i++) {
            int ni=dir[i][0]+tp.f, nj= dir[i][1]+tp.s;
            if(ni >=0 && ni<n && nj>=0 && nj<m && !vis[ni][nj] && str[ni][nj]!='.') {
                if(str[ni][nj]!=str[tp.f][tp.s]) dq.push_back({ni,nj}),dp[ni][nj]=ans+1;
                else dq.push_front({ni,nj}),dp[ni][nj]=ans;
                
                vis[ni][nj]=1;
            }
        }
    }
    cout<<ans<<"\n";
}
 
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    int t = 1; while (t--) solve();
    return 0;
}

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