Я работаю над задачей обхода графа, и моя программа дает неправильный ответ на больших входных данных, а именно, когда 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;
}