Здравствуйте! Недавно решал задачу Timus 1635 "мнемоника и палиндромы". Столкнулся с проблемой: как в C++ создать двумерный массив 4000*4000? Массив graph[4000][4000]. Если я делаю graph[4000][4000], то компилятор сообщает
Runtime error (access violation) ,а если graph[400][400],то завал на 17 тесте. Как решить эту проблему? И можно ли сделать обход в ширину без использования матрицы смежности?
http://e-maxx.ru/algo/bfs
Делайте список смежности. Про него хорошо написано тут в комментариях или тут
Если так уж хочется двумерный массив 4000*4000, то можно использовать вектора:
но ̶н̶а̶ ̶C̶F̶,̶н̶а̶п̶р̶и̶м̶е̶р̶,̶ это потребляет ~64MB памяти
Про обход в ширину можно посмотреть здесь и здесь — лекции ЛКШ
Ну так двухмерный массив будет требоватт 64 мегабайта.
Я это и имел в виду
Access violation возникает потому что память под переменные внутри функций выделяется из стека. Массив интов 4000*4000 в стек не влезает, отсюда обращение к недопустимому участку памяти.
Достаточно объявить массив глобально, то есть
изнутриснаружи функции, и ошибка исчезнет. Но конкретно для BFS лучше использовать список смежности.Я понял так: ВНУТРИ функции плохо, а вот если ИЗНУТРИ, то хорошо.
Внутри функции размер переменных ограничен размером стека.
ИзнутриСнаружи функций размер переменных ограничен размером оперативки.я к тому что, изнутри — слово непонятное. Кстати, изнутри антоним слова снаружи
Прошу прощения, совсем неграмотный стал. Исправился.
Здесь можно обойтись массивом boolean 4000 x 4000, он будет занимать 16 мегабайт.
Можем еще битовое сжатие применить