제출 #1359585

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

tracks

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int H, W;
vector<vector<char>> grid;
int rD[] = {0,1,0,-1};
int cD[] = {1,0,-1,0};

int BFS(int startR, int startC) {
    deque<pair<int, int>> q;
    q.push_front({ startR, startC });
    vector<vector<int>> sol(H, vector<int>(W, 0));
    sol[startR][startC] = 1;
    int ans = 1;

    while (!q.empty()) {
        auto [curR, curC] = q.front(); q.pop_front();
        ans = max(ans, sol[curR][curC]);

        for (int i = 0; i < 4; ++i) {
            int nR = curR + rD[i];
            int nC = curC + cD[i];

            if (nR < 0 || nR >= H || nC < 0 || nC >= W || grid[nR][nC] == '.' || sol[nR][nC] != 0) continue;

            if (grid[curR][curC] == grid[nR][nC]) {
                sol[nR][nC] = sol[curR][curC];
                q.push_front({ nR,nC });
            }
            else {
                sol[nR][nC] = sol[curR][curC] + 1;
                q.push_back({ nR,nC });
            }            
        }
    }

    return ans;
}

int main()
{
    cin >> H >> W;
    grid.assign(H, vector<char>(W));

    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            cin >> grid[i][j];
        }
    }

    cout << BFS(0, 0);
}

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