제출 #700221

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

tracks

//0/1 bfs each element, find max
#include <iostream>
#include <queue>

using namespace std;
using pii = pair<int, int>;
int h,w, ans=1;
string field[4001];
bool used[4001][4001];
pii dir[4] = {{0,1},{1,0},{-1,0},{0,-1}};
pii operator+(pii a, pii b){
    return make_pair(a.first+b.first, a.second+b.second);
}
deque<pii> q;
deque<int> moves;
deque<char> sign;
bool out(pii a){
    if (a.first < 0 || a.second < 0 || a.first >= h || a.second >= w) return true;
    return false;
}


int main(){
    cin >> h >> w;
    for (int i=0; i<h; i++){
        cin >> field[i];
    }
    q.push_back({0,0});
    moves.push_back(1);
    sign.push_back(field[0][0]);
    used[0][0] = true;
    while (!q.empty()){
        pii cur = q.front(); q.pop_front();
        int curmove = moves.front(); moves.pop_front();
        char cursign = sign.front(); sign.pop_front();
        ans = max(ans, curmove);
        for (int i=0; i<4; i++){
            pii newp = cur + dir[i];
            if (out(newp) || field[newp.first][newp.second] == '.' || used[newp.first][newp.second]) continue;
            if (field[newp.first][newp.second] == cursign){
                sign.push_front(cursign);
                moves.push_front(curmove);
                q.push_front(newp);
            } 
            else{
                sign.push_back(field[newp.first][newp.second]);
                moves.push_back(curmove+1);
                q.push_back(newp);
            }
            used[newp.first][newp.second] = true;
        }
    }
    cout << ans;
}

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