Cod sursa(job #2146392)

Utilizator PondorastiAlex Turcanu Pondorasti Data 27 februarie 2018 22:47:13
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream in("castel.in");
ofstream out("castel.out");

const int MAX_N = 150, MAX_K = 22500;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int rows, columns, start, answer = 1, counter;
int map[MAX_N + 2][MAX_N + 2], requiredKey[MAX_N + 2][MAX_N + 2];
bool isVisited[MAX_N + 2][MAX_N + 2], key[MAX_K + 2];
vector<pair<int, int> > positions;

int main() {
    in >> rows >> columns >> start;
    for (int i = 1; i <= rows; ++i) {
        for (int j = 1; j <= columns; ++j) {
            in >> requiredKey[i][j];
            map[i][j] = ++counter;
            if (counter == start) {
                key[requiredKey[i][j]] = true;
                isVisited[i][j] = true;
                positions.push_back({i, j});
            }
        }
    }
    
    while (true) {
        int currentAnswer = answer;
        for (auto it: positions) {
            for (int d = 0; d < 4; ++d) {
                int x = dx[d] + it.first;
                int y = dy[d] + it.second;
                if (!isVisited[x][y] && key[requiredKey[x][y]]) {
                    ++answer;
                    key[map[x][y]] = true;
                    isVisited[x][y] = true;
                    positions.push_back({x, y});
                }
            }
        }
        if (answer == currentAnswer)
            break;
    }
    out << answer << "\n";
    return 0;
}