Неправильный ответ на больших входах - PullRequest
0 голосов
/ 13 апреля 2019

Я работаю над задачей обхода графа, и моя программа дает неправильный ответ на больших входных данных, а именно, когда n = 100. Моя программа дает правильный ответ на меньшие значения n, такие как 5 и 10, но дает неправильный ответ, когда n = 100. Кто-нибудь может мне помочь найти почему? Вот формулировка проблемы:

http://usaco.org/index.php?page=viewproblem2&cpid=570

(мой код указан ниже)

Я уже добавил код проверки границ, чтобы удостовериться, что у меня нет доступа за границы в моем 2D-массиве, и проверил его вручную на больших входах, когда n = 100, и он работает там, однако он дает неправильный ответ на официальном тестовые данные, где n = 100. Кто-нибудь может понять, почему? Мой код ниже.

#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
typedef pair<int, int> pii;

int a[102][102];
vector<pii> adj[102][102];
bool illuminated[102][102];
int n, m, ans = 1;

bool ok(int row, int col) {
bool good = false;
    if ((row - 1) >= 1) {
        if (illuminated[row - 1][col]) good = true;
    }
    if ((row + 1) <= n) {
        if (illuminated[row + 1][col]) good = true;
    }
    if ((col - 1) >= 1) {
        if (illuminated[row][col - 1]) good = true;
    }
    if ((col + 1) <= n) {
        if (illuminated[row][col + 1]) good = true;
    }
    return good;
}

void illuminate(int row, int col, queue<pii> &toVisit) {
    vector<pii>::iterator it;
    for (it = adj[row][col].begin(); it != adj[row][col].end(); it++) {
        if (!illuminated[it->first][it->second]) {
            illuminated[it->first][it->second] = true;
            toVisit.push(make_pair(it->first, it->second));
            ans++;
        }
    }
}

void visit(int row, int col) {
    queue<pii> toVisit;
    //toVisit.push(make_pair(row, col));
    illuminate(row, col, toVisit);
    while (!toVisit.empty()) {
        pair<int, int> p = toVisit.front();
        toVisit.pop();
        if (ok(p.first, p.second)) {
            illuminate(p.first, p.second, toVisit);
        }
    }
}

int main() {
    ofstream fout("lightson.out");
    ifstream fin("lightson.in");
    for (int i = 0; i < 102; i++) {
        for (int j = 0; j < 102; j++) {
            illuminated[i][j] = false;
        }
    }
    illuminated[1][1] = true;
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, x, y;
        fin >> a >> b >> x >> y;
        adj[a][b].push_back(make_pair(x, y));
    }
    visit(1, 1);
    fout << ans << "\n";
    return 0;
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...