제출 #1278918

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

tracks

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

const int directie[2][4] = {{-1 , 0 , 1 , 0} , {0 , 1 , 0 , -1}};
int distanta[4000][4000];
char tip[4000][4001];

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int linii , coloane;
    cin >> linii >> coloane;

    for (int linie = 0 ; linie < linii ; linie++)
        { cin >> tip[linie]; }
    
    int maxim = 1;
    distanta[0][0] = 1;
    deque < pair <int , int> > ramas;
    ramas.emplace_back(0 , 0);
    while (!ramas.empty())
    {
        const pair <int , int> nod = ramas.front();
        maxim = max(maxim , distanta[nod.first][nod.second]);
        ramas.pop_front();
        
        for (int indice = 0 ; indice < 4 ; indice++)
        {
            const pair <int , int> vecin = {nod.first + directie[0][indice] , nod.second + directie[1][indice]};
            if (0 <= vecin.first && vecin.first < linii && 0 <= vecin.second && vecin.second < coloane && tip[vecin.first][vecin.second] != '.' && !distanta[vecin.first][vecin.second])
            {
                distanta[vecin.first][vecin.second] = distanta[nod.first][nod.second] + (tip[vecin.first][vecin.second] == tip[nod.first][nod.second] ? 0 : 1);
                if (tip[vecin.first][vecin.second] == tip[nod.first][nod.second]) { ramas.push_front(vecin); }
                else { ramas.push_back(vecin); }
            }
        }
    }

    cout << maxim;
    return 0;
}

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