제출 #882791

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
882791		vincentbucourt1	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	595 ms	130704 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

string pic[4000];
int minLen[4000][4000];
int H, W;

int Y[4] = {0, 0, 1, -1}, X[4] = {1, -1, 0, 0};

bool inRec(int Y, int X){
    return (Y > -1 && Y < H && X > -1 && X < W && pic[Y][X] != '.');
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> H >> W;
    
    for (int i = 0; i < H; i++){
        cin >> pic[i];
    }
    
    deque<pair<int, int>> Q; // {X, Y}
    pair<int, int> on;
    int M = 0;
    Q.push_front({0, 0});
    minLen[0][0] = 1;
    
    while (!Q.empty()){
        on = Q.front();
        Q.pop_front();
        M = max(M, minLen[on.second][on.first]);
        
        for (int i = 0; i < 4; i++){
            
            int onX = on.first + X[i], onY = on.second + Y[i];
            
            if (inRec(onY, onX) && minLen[onY][onX] == 0){
                if (pic[on.second][on.first] == pic[onY][onX]){
                    Q.push_front({onX, onY});
                    minLen[onY][onX] = minLen[on.second][on.first];
                }
                else{
                    Q.push_back({onX, onY});
                    minLen[onY][onX] = minLen[on.second][on.first] + 1;
                }
            }
        }
    }
    
    cout << M;
}

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