namespace Forest{  

using location_t = std::pair<size_t, size_t>;
using locations_t = std::vector<location_t>;
using path_t = locations_t;
using paths_t = std::vector<path_t>;

static constexpr char START = 'M'; 
static constexpr char DESTINATION = '*'; 
static constexpr char BLOCKED = 'X';
static constexpr std::array<std::pair<int, int>, 4> directions = {
    std::make_pair(-1, 0), std::make_pair(0, 1),
    std::make_pair(1, 0), std::make_pair(0, -1)};

location_t findLocation(
    std::vector<std::string>  const &,
    char const &
);

paths_t collectPathes(
    std::vector<std::string> &,
    location_t const &
);

size_t countHints(
    paths_t const & _pathes, 
    location_t const & _start
);

std::string countLuck(
    std::vector<std::string> & _forest,
    int const & _hints
){
    auto const start = findLocation(_forest, START);
    auto pathes = collectPathes(_forest, start);
    auto hintsUsed = countHints(pathes, start);
    std::cout << _hints << " " << hintsUsed << '\n';
    return _hints == static_cast<int>(hintsUsed) ? "Impressed" : "Oops!";
}

inline location_t findLocation(
    std::vector<std::string>  const & _forest,
    char const & _value
){
    auto const & szRows = _forest.size();
    auto const & szCols = _forest.front().size();
    auto destination = std::make_pair(std::numeric_limits<size_t>::max(),
        std::numeric_limits<size_t>::max());
    for(size_t r = 0; r < szRows; ++r){
        for(size_t c = 0; c < szCols; ++c){
            if(_forest.at(r).at(c) != _value){
                continue;;
            }
            return {r, c};
        }
    }
    return destination; 
}

paths_t collectPathes(
    std::vector<std::string> & _forest,
    location_t const & _start
){
    auto const destination = findLocation(_forest, DESTINATION);
    _forest.at(_start.first).at(_start.second) = BLOCKED;
    auto nextLocationOptions = locations_t();
    nextLocationOptions.reserve(directions.size());
    size_t rowNext = std::numeric_limits<size_t>::max();
    size_t colNext = rowNext;
    auto pathes = paths_t();
    pathes.emplace_back(path_t({_start}));
    auto const & szRows = _forest.size();
    auto arrived = false;
    auto const & szCols = _forest.front().size();
    for(size_t pathIndx = 0, locationIndx = 0; pathIndx < pathes.size()
        && !arrived;
    ){
        auto & path = pathes.at(pathIndx);
        auto & location = path.at(locationIndx);
        for(auto const & direction : directions){
            rowNext = location.first + direction.first;
            colNext = location.second + direction.second;
            if( rowNext < 0 || szRows <= rowNext ||
                colNext < 0 || szCols <= colNext ||
                _forest.at(rowNext).at(colNext) == BLOCKED
            ){
                continue;
            }
            _forest.at(rowNext).at(colNext) = BLOCKED;
            nextLocationOptions.emplace_back(rowNext, colNext);
        }
        if(nextLocationOptions.size() == 1){
            path.emplace_back(nextLocationOptions.back());
            ++locationIndx;
            if(nextLocationOptions.back() == destination){
                arrived = true;
            }
            nextLocationOptions.clear();
            continue;
        }
        for(auto const & nextLocationOption: nextLocationOptions){
            pathes.emplace_back(path_t({location}));
            pathes.back().emplace_back(nextLocationOption);
            if(nextLocationOption == destination){
                arrived = true;
            }
        }
        ++pathIndx;
        locationIndx = 1;
        nextLocationOptions.clear();
    }
    return pathes;
}

inline size_t countHints(
    paths_t const & _pathes, 
    location_t const & _start
){
    size_t hintsUsed = 0;
    for(auto path = std::rbegin(_pathes), pathPrev = path + 1;
        pathPrev != rend(_pathes);
        path = pathPrev,  pathPrev = path + 1
    ){
        ++hintsUsed;
        if(path->front() == _start){
            break;
        }
        while(path->front() != pathPrev->back()){
            ++pathPrev;
        }
    }
    return hintsUsed;
}

} // namespace Forest