Submission #953337

#	Time	Username	Problem	Language	Result	Execution time	Memory
953337		snowman	Mecho (IOI09_mecho)	C++17	Compilation error	0 ms	0 KiB

mecho

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>

using namespace std;

struct Cell {
    int x, y;
    Cell(int _x, int _y) : x(_x), y(_y) {}
};

bool isValid(int x, int y, int n) {
    return x >= 0 && x < n && y >= 0 && y < n;
}

int bfs(vector<string>& forest, Cell start, Cell home, int max_steps) {
    int n = forest.size();
    vector<pair<int, int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    unordered_set<int> visited;
    queue<pair<Cell, int>> q;
    q.push({start, 0});
    visited.insert(start.x * n + start.y);

    while (!q.empty()) {
        Cell current = q.front().first;
        int steps = q.front().second;
        q.pop();

        if (current.x == home.x && current.y == home.y)
            return steps;

        if (steps >= max_steps)
            return -1;

        for (auto& dir : directions) {
            int nx = current.x + dir.first;
            int ny = current.y + dir.second;
            if (isValid(nx, ny, n) && forest[nx][ny] != 'T' && visited.find(nx * n + ny) == visited.end()) {
                visited.insert(nx * n + ny);
                q.push({{nx, ny}, steps + 1});
            }
        }
    }

    return -1;
}

int findMaxHoneyTime(vector<string>& forest, Cell start, Cell home, int max_steps) {
    int max_time = -1;
    unordered_set<int> bees_spread;
    int n = forest.size();

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (forest[i][j] == 'H')
                bees_spread.insert(i * n + j);
        }
    }

    for (int i = 1; i <= max_steps; ++i) {
        int time_taken = bfs(forest, start, home, i);
        if (time_taken == -1)
            break;
        max_time = max(max_time, time_taken);

        unordered_set<int> temp;
        for (auto& cell : bees_spread) {
            int x = cell / n;
            int y = cell % n;
            for (auto& dir : {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}) {
                int nx = x + dir.first;
                int ny = y + dir.second;
                if (isValid(nx, ny, n) && forest[nx][ny] != 'T')
                    temp.insert(nx * n + ny);
            }
        }
        bees_spread.insert(temp.begin(), temp.end());
    }

    return max_time;
}

int main() {
    int N, S;
    cin >> N >> S;
    vector<string> forest(N);
    for (int i = 0; i < N; ++i)
        cin >> forest[i];

    Cell start, home;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (forest[i][j] == 'M')
                start = {i, j};
            else if (forest[i][j] == 'D')
                home = {i, j};
        }
    }

    int max_time = findMaxHoneyTime(forest, start, home, S);
    cout << max_time << endl;

    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int findMaxHoneyTime(std::vector<std::__cxx11::basic_string<char> >&, Cell, Cell, int)':
mecho.cpp:71:63: error: unable to deduce 'std::initializer_list<auto>&&' from '{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}'
   71 |             for (auto& dir : {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}) {
      |                                                               ^
mecho.cpp:71:63: note:   couldn't deduce template parameter 'auto'
mecho.cpp: In function 'int main()':
mecho.cpp:91:10: error: no matching function for call to 'Cell::Cell()'
   91 |     Cell start, home;
      |          ^~~~~
mecho.cpp:10:5: note: candidate: 'Cell::Cell(int, int)'
   10 |     Cell(int _x, int _y) : x(_x), y(_y) {}
      |     ^~~~
mecho.cpp:10:5: note:   candidate expects 2 arguments, 0 provided
mecho.cpp:8:8: note: candidate: 'constexpr Cell::Cell(const Cell&)'
    8 | struct Cell {
      |        ^~~~
mecho.cpp:8:8: note:   candidate expects 1 argument, 0 provided
mecho.cpp:8:8: note: candidate: 'constexpr Cell::Cell(Cell&&)'
mecho.cpp:8:8: note:   candidate expects 1 argument, 0 provided
mecho.cpp:91:17: error: no matching function for call to 'Cell::Cell()'
   91 |     Cell start, home;
      |                 ^~~~
mecho.cpp:10:5: note: candidate: 'Cell::Cell(int, int)'
   10 |     Cell(int _x, int _y) : x(_x), y(_y) {}
      |     ^~~~
mecho.cpp:10:5: note:   candidate expects 2 arguments, 0 provided
mecho.cpp:8:8: note: candidate: 'constexpr Cell::Cell(const Cell&)'
    8 | struct Cell {
      |        ^~~~
mecho.cpp:8:8: note:   candidate expects 1 argument, 0 provided
mecho.cpp:8:8: note: candidate: 'constexpr Cell::Cell(Cell&&)'
mecho.cpp:8:8: note:   candidate expects 1 argument, 0 provided