제출 #1361525

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

tracks

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

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};

int main() {
    // ??????
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int H, W;
    cin >> H >> W;
    vector<string> grid(H);
    for (int i = 0; i < H; ++i) {
        cin >> grid[i];
    }
    
    // dist[r][c] ???????? (r,c) ???????
    // ??? 0 ?????
    vector<vector<int>> dist(H, vector<int>(W, 0));
    deque<pair<int, int>> dq;
    
    // ???????????????????????????????
    if (grid[0][0] != '.') {
        dist[0][0] = 1;          // ?????
        dq.push_back({0, 0});
    }
    
    int ans = 0;   // ????????? 0?????? 1
    
    while (!dq.empty()) {
        // ???????C++11 ?? front() ?? pop_front()
        pair<int, int> cur = dq.front();
        dq.pop_front();
        int r = cur.first;
        int c = cur.second;
        
        // ??????
        if (dist[r][c] > ans) ans = dist[r][c];
        
        // ??????
        for (int dir = 0; dir < 4; ++dir) {
            int nr = r + dx[dir];
            int nc = c + dy[dir];
            
            // ???? ?? ???????????
            if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue;
            if (grid[nr][nc] == '.') continue;
            if (dist[nr][nc] != 0) continue;
            
            if (grid[nr][nc] == grid[r][c]) {
                // ??????? 0??????????
                dist[nr][nc] = dist[r][c];
                dq.push_front({nr, nc});
            } else {
                // ??????? 1???? 1?????
                dist[nr][nc] = dist[r][c] + 1;
                dq.push_back({nr, nc});
            }
        }
    }
    
    cout << ans << '\n';
    return 0;
}

• 서브태스크 1: 30 / 30
• 서브태스크 2: 70 / 70