Здравствуйте! Недавно решал задачу Timus 1635 "мнемоника и палиндромы". Столкнулся с проблемой: как в C++ создать двумерный массив 4000*4000? Массив graph[4000][4000]. Если я делаю graph[4000][4000], то компилятор сообщает
Runtime error (access violation) ,а если graph[400][400],то завал на 17 тесте. Как решить эту проблему? И можно ли сделать обход в ширину без использования матрицы смежности?
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3657 |
| 3 | jiangly | 3638 |
| 4 | turmax | 3442 |
| 5 | tourist | 3380 |
| 6 | Um_nik | 3353 |
| 7 | strapple | 3350 |
| 8 | squareOf105 | 3346 |
| 9 | heuristica | 3322 |
| 10 | maroonrk | 3310 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 151 |
| 3 | maspy | 150 |
| 4 | AmShZ | 144 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 135 |
| 9 | maroonrk | 133 |
| 10 | qwexd | 130 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 18.10.2026 20:46:00 (g2).
Десктопная версия, переключиться на мобильную.
При поддержке
http://e-maxx.ru/algo/bfs
Делайте список смежности. Про него хорошо написано тут в комментариях или тут
Если так уж хочется двумерный массив 4000*4000, то можно использовать вектора:
но ̶н̶а̶ ̶C̶F̶,̶н̶а̶п̶р̶и̶м̶е̶р̶,̶ это потребляет ~64MB памяти
Про обход в ширину можно посмотреть здесь и здесь — лекции ЛКШ
Ну так двухмерный массив будет требоватт 64 мегабайта.
Я это и имел в виду
Access violation возникает потому что память под переменные внутри функций выделяется из стека. Массив интов 4000*4000 в стек не влезает, отсюда обращение к недопустимому участку памяти.
Достаточно объявить массив глобально, то есть
изнутриснаружи функции, и ошибка исчезнет. Но конкретно для BFS лучше использовать список смежности.Я понял так: ВНУТРИ функции плохо, а вот если ИЗНУТРИ, то хорошо.
Внутри функции размер переменных ограничен размером стека.
ИзнутриСнаружи функций размер переменных ограничен размером оперативки.я к тому что, изнутри — слово непонятное. Кстати, изнутри антоним слова снаружи
Прошу прощения, совсем неграмотный стал. Исправился.
Здесь можно обойтись массивом boolean 4000 x 4000, он будет занимать 16 мегабайт.
Можем еще битовое сжатие применить