Submission #654246

#	Time	Username	Problem	Language	Result	Execution time	Memory
654246		gillambas	Mecho (IOI09_mecho)	C++14	24 / 100	1093 ms	9836 KiB

mecho

#include <iostream>
#include <queue>
#include <stack>
#include <vector>

// Global variables
int N{ 0 };
int S{ 0 };

bool isInBounds(int i, int j) {
  return (i >= 0 && i < N && j >= 0 && j < N);
}

bool isBearWalkable(int i, int j, const std::vector<std::string>& forest) {
  return (forest[i][j] == 'G' || forest[i][j] == 'D');
}

bool isBeeWalkable(int i, int j, const std::vector<std::string>& forest) {
  return (forest[i][j] == 'G' || forest[i][j] == 'M');
}

bool isNotVisited(int i, int j, const std::vector<std::vector<bool>>& visited) {
  return (!visited[i][j]);
}

bool isBearCandidate(int i, int j, const std::vector<std::string>& forest, const std::vector<std::vector<bool>>& visited) {
  return (  isInBounds(i, j)
         && isBearWalkable(i, j, forest)
         && isNotVisited(i, j, visited) );
}

bool isBeeCandidate(int i, int j, const std::vector<std::string>& forest) {
  return (  isInBounds(i, j)
         && isBeeWalkable(i, j, forest));
}

void addBeeCandidate(int i, int j, int current_i, int current_j, std::vector<std::string>& forest, std::stack<std::pair<int,int>>& new_bees_positions) {
  if (isBeeCandidate(i, j, forest)) {
    forest[i][j] = 'H';
    new_bees_positions.push(std::make_pair(i, j));
  }
}

std::stack<std::pair<int, int>> spreadBees(std::stack<std::pair<int, int>>& current_bees_positions, std::vector<std::string>& forest) {
  std::stack<std::pair<int, int>> new_bees_positions;

  while (!current_bees_positions.empty()) {
    int current_i{ current_bees_positions.top().first };
    int current_j{ current_bees_positions.top().second };
    current_bees_positions.pop();

    addBeeCandidate(current_i - 1, current_j    , current_i, current_j, forest, new_bees_positions);
    addBeeCandidate(current_i + 1, current_j    , current_i, current_j, forest, new_bees_positions);
    addBeeCandidate(current_i    , current_j - 1, current_i, current_j, forest, new_bees_positions);
    addBeeCandidate(current_i    , current_j + 1, current_i, current_j, forest, new_bees_positions);
  }

  return new_bees_positions;
}

void addBearCandidate( int i, int j, int current_i, int current_j
  , const std::vector<std::string>& forest
  , std::vector<std::vector<bool>>& visited
  , std::vector<std::vector<int>>& dist
  , std::vector<std::vector<std::pair<int, int>>>& trajectory
  , std::queue<std::pair<int,int>>& q) {
  
  if (isBearCandidate(i, j, forest, visited)) {
    q.push(std::make_pair(i, j));
    visited[i][j] = true;
    dist[i][j] = dist[current_i][current_j] + 1;
    trajectory[i][j] = std::make_pair(current_i, current_j);
  }
}

int findShortestPath(const std::vector<std::string>& forest, const std::pair<int, int>& start, const std::pair<int, int>& end) {
  std::vector<std::vector<bool>>                visited(N, std::vector<bool>(N, false));
  std::vector<std::vector<int>>                 dist(N, std::vector<int>(N, 0));
  std::vector<std::vector<std::pair<int, int>>> trajectory(N, std::vector<std::pair<int, int>>(N));

  std::queue<std::pair<int, int>> q;
  q.push(start);

  int current_i{ start.first };
  int current_j{ start.second };

  visited[current_i][current_j] = true;

  while (!q.empty() && forest[current_i][current_j] != 'D') {
    current_i = q.front().first;
    current_j = q.front().second;
    q.pop();

    if (forest[current_i][current_j] != 'D') {
      addBearCandidate(current_i - 1, current_j    , current_i, current_j, forest, visited, dist, trajectory, q);
      addBearCandidate(current_i + 1, current_j    , current_i, current_j, forest, visited, dist, trajectory, q);
      addBearCandidate(current_i    , current_j - 1, current_i, current_j, forest, visited, dist, trajectory, q);
      addBearCandidate(current_i    , current_j + 1, current_i, current_j, forest, visited, dist, trajectory, q);
    }
  }
  /*
  std::cout << dist[3][6] << std::endl;

  int i{ 3 };
  int j{ 6 };

  while (! (i == start.first && j == start.second)) {
    std::cout << trajectory[i][j].first << " " << trajectory[i][j].second << std::endl;
    int temp_i{ trajectory[i][j].first };
    int temp_j{ trajectory[i][j].second };
    i = temp_i;
    j = temp_j;
  }
  */
  return dist[end.first][end.second];
}

int timeToHome(int pathLength) {
  int time { pathLength / S };

  if (pathLength % S != 0)
    ++time;

  return time;
}

void parser(std::vector<std::string>& forest) {
  std::cin >> N >> S;

  for (int i = 0; i < N; ++i) {
    std::string row;
    std::cin >> row;
    forest.push_back(row);
  }
}

void getPositions(std::vector<std::string>& forest, std::stack < std::pair<int, int>>& current_bees_positions, std::pair<int, int>& start, std::pair<int, int>& end) {
  for (int i=0; i<N; ++i)
    for (int j=0; j<N; ++j)
      if (forest[i][j] == 'M') {
        start.first  = i;
        start.second = j;
      }
      else if (forest[i][j] == 'D') {
        end.first  = i;
        end.second = j;
      }
      else if (forest[i][j] == 'H')
        current_bees_positions.push(std::make_pair(i, j));
}

void printForest(const std::vector<std::string>& forest) {
  for (size_t i = 0; i < N; ++i)
    std::cout << forest[i] << std::endl;
}

int main() {
  std::vector<std::string> forest;
  parser(forest);

  std::stack < std::pair<int, int>> current_bees_positions;
  std::pair<int, int> start{ 0,0 };
  std::pair<int, int> end{ 0,0 };
  getPositions(forest, current_bees_positions, start, end);

  int dist{ 0 };
  int temp_dist{ 0 };
  int bees_time{ 0 };

  do {
    temp_dist = findShortestPath(forest, start, end);

    if (temp_dist != 0) {
      current_bees_positions = spreadBees(current_bees_positions, forest);
      //printForest(forest);
      ++bees_time;
      dist = temp_dist;
    }

  } while (temp_dist !=0 );

  --bees_time;
  --bees_time;

//  int time{ timeToHome(dist) - bees_time + 1};

  //std::cout << timeToHome(dist) << std::endl;
  std::cout << bees_time;// << std::endl;
  //std::cout << time << std::endl;

  /*
  findShortestPath(forest, start);

  std::stack < std::pair<int, int>> next_bees_positions;

  spreadBees(current_bees_positions, next_bees_positions, forest);


  std::stack < std::pair<int, int>> next_next_bees_positions;

  spreadBees(next_bees_positions, next_next_bees_positions, forest);
  */
}

Compilation message (stderr)

mecho.cpp: In function 'void printForest(const std::vector<std::__cxx11::basic_string<char> >&)':
mecho.cpp:153:24: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  153 |   for (size_t i = 0; i < N; ++i)
      |                      ~~^~~
mecho.cpp: In function 'int main()':
mecho.cpp:166:7: warning: variable 'dist' set but not used [-Wunused-but-set-variable]
  166 |   int dist{ 0 };
      |       ^~~~

• Subtask 1: 24 / 100