제출 #578092

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

tracks

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
    int h, w; cin >> h >> w;
    char meadow[h][w]; int depth[h][w];
    for(int y=0; y<h; ++y) {
        for(int x=0; x<w; ++x) {
            cin >> meadow[y][x];
            depth[y][x] = -1;
        }
    }
    int deltaY[4] = {-1, 0, 1, 0};
    int deltaX[4] = {0, 1, 0, -1};
    deque<pair<int, int> > bfs;
    pair<int, int> start; start.first = 0;
    start.second = 0; bfs.push_front(start);
    depth[0][0] = 1; int animals = 1;
    while(!bfs.empty()) {
        int y = bfs.front().first;
        int x = bfs.front().second;
        bfs.pop_front();
        animals = max(animals, depth[y][x]);
        for(int i=0; i<4; ++i) {
            pair<int, int> next;
            next.first = y + deltaY[i];
            next.second = x + deltaX[i];
            if(next.first >= 0 && next.first < h
            && next.second >= 0 && next.second < w
            && meadow[next.first][next.second] != '.'
            && depth[next.first][next.second] == -1) {
                if(meadow[y][x] == meadow[next.first][next.second]) {
                    depth[next.first][next.second] = depth[y][x];
                    bfs.push_front(next);
                }
                else {
                    depth[next.first][next.second] = depth[y][x] + 1;
                    bfs.push_back(next);
                }
            }
        }
    }
    cout << animals << "\n";
    return 0;
}

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