제출 #1273341

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

tracks

#include <bits/stdc++.h>
#define int long long
using namespace std;
int h,w,d[4001][4001],res,dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
string s[4001];
deque <pair <int, int>> q;
int32_t main(){
    cin >> h >> w;
    for (int i=0;i<h;i++)
        cin >> s[i];
    q.push_back({0,0});
    d[0][0]=1;
    while (!q.empty()){
        auto [x,y]=q.front();
        q.pop_front();
        res=d[x][y];
        for (int i=0;i<4;i++){
            int x2=x+dx[i],y2=y+dy[i];
            if (x2>=0&&x2<h&&y2>=0&&y2<w&&s[x2][y2]!='.'){
                int w=(s[x2][y2]!=s[x][y]);
                if (!d[x2][y2]){
                    d[x2][y2]=d[x][y]+w;
                    if (w)
                        q.push_back({x2,y2});
                    else
                        q.push_front({x2,y2});
                }
            }
        }
    }
    cout << res;
}

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