Не работает рекурсия

[венди спенсер]

В общем коротко о сути проблемы:
Приспичило мне написать консольную версию Сапёра на C++ 5.02

Все хорошо, кроме одного:
В оригинале, когда открываешь пустую клетку - открываются все соседние пустые клетки вплоть до клеток с цифрами. Коряво объяснил - но суть, уверен, понятна.
Это легче всего в мозгу мне приходит в голову в виде рекурсии.

Чтобы не разбираться с нахождением на краю или в углу поля я увеличил его размеры со всех четырех сторон. То есть вместо поля 9х9 получилось 11х11 (это все обозначается как статический двумерный целочисленный массив).
По моей задумке - это должно было лишить меня проблем.
Более того НОВЫМ границам я задал значения в каждой ячейке равными 11 (пустая клетка соответственно - 0, мина - 9, а все остальные - количество мин.)

Извините, я не знаю спец. сайтов для "подсветки" - если дадите ссылку - буду признателен.
На тот, что сверху написан я зашел. Но к моему стыду я не разобрался что там да как...
Поэтому вот это вот - та рекурсия, которую я написал:

void rek(y,x)
{
c[y][x]=a[y][x]+48; //открываю текущую клетку.
if(c[y][x]=='0') // если она пустая, то выполняю следующее.
{
if(a[y][x-1]==0)
rek(y,x-1);
else
c[y][x-1]=a[y][x-1]+48; // проверяю - пустая ли клетка сбоку - если да - тогда закидываю ее координаты в рекурсивную ф-ию. если нет - просто открываю ее.

if(a[y-1][x]==0)
rek(y-1,x);
else
c[y-1][x]=a[y-1][x]+48;

if(a[y+1][x]==0)
rek(y+1,x);
else
c[y+1][x]=a[y+1][x]+48;

if(a[y][x+1]==0)
rek(y,x+1);
else
c[y][x+1]=a[y][x+1]+48;

if(a[y-1][x+1]==0)
rek(y-1,x+1);
else
c[y-1][x+1]=a[y-1][x+1]+48;

if(a[y+1][x-1]==0)
rek(y+1,x-1);
else
c[y+1][x-1]=a[y+1][x-1]+48;

if(a[y+1][x+1]==0)
rek(y+1,x+1);
else
c[y+1][x+1]=a[y+1][x+1]+48;

if(a[y-1][x-1]==0)
rek(y-1,x-1);
else
c[y-1][x-1]=a[y-1][x-1]+48;
}

}


Так она вызывается в программе:

if(f=='x' && a[y][x]!=9) // f - переменная char. 'x' - элемент управления, так сказать (открытие поля). То есть: "Открыв поле, если там не мина."
{
rek(y,x); // х, у - координаты на поле.
gotoxy(1,1);
Output(); // это просто вывод массива.
gotoxy(x,y);
}

Так вот сама проблема. При запуске выдается сообщение такого рода: Thread stopped и бла-бла-бла.
Как быдто я выхожу за размер масива...

Причем такая ошибка только если у меня в рекурсивной ф-ии идет проверка ПРОТИВОПОЛОЖНЫХ от начальной клетки ячеек.
то есть например - вышее ее и ниже. (если например выше и правее, в верхнем левом углу и верхнем правом углу - тогда работает).

В общем вопрос - как это можно исправить.
Не обязательно код - можно просто подкинуть идею.
Заранее спасибо.

@темы: C++

Comments

[венди спенсер]

Загоняйте в компилятор - он вам всё расскажет ).

Желательно if (a[x][y] == -1) return; в начале поставить, для читаемости например.

ага, спасибо большое.
да - надеюсь с компиллятором проблем не будет =)

[венди спенсер]

Слушатель
Спасибо огромное. Всё работает отлично.

[Слушатель]

Catch By Madness
Рад слышать ). Удачи в дальнейшей деятельности ).

[венди спенсер]

спасибо =)

[венди спенсер]

Слушатель , вот еще спросить хотел:
вот в моей программе я использовал два массива:
1) числовой (в нем 9 - это мины а все остальные числа - кол-во мин вокруг считаются сразу после создаия массива и расстановки бомб)
2) символьный (собственно само поле)

первый массив я использовал для того, чтобы проверять наличие мины на данной клетке или количества мин.
все остальное было на втором массиве. В частности постановка/снятие флажка (когда нажимаешь кнопку "поставить/снять флажок", проверяю, что находится в этой клетке и после этого выбираю нужный вариант из двух...)

вот. а потом мне стукнула идея, использовать только один массив. И он должен быть символьный.
на нем отметить бомбы. при открытии клетки каждый раз считать количество мин вокруг нее и присваивать это значение соответствующему элементу массива.
разница правда вроде нету: задавать значение каждому полю сначала или постепенно, но так меньше памяти надо, и вывод будет удобнее (потому что у меня после каждого хода ВСЁ поле банально обновлялось, а так будет по одному символу.)

Но тут такая проблема. Проблема с постановкой/снятием флажков.

Пусть у меня маасив (поле) состоит изначально из символов ' ' и 'B'. ну, логично.
Поставить/снять флажок в таком случае не проблема, я это все беру из своего готового варианта.
Но есть вероятность "потерять" где находится мина, если поставить два флажка: один на мину, а другой не на мину.
Блин... Криво объясняю...

Или может просто создать двумерный массив с координатами мин, а все остальное считать уже по ходу?..

Просто вот задумался...

[Слушатель]

Catch By Madness
потому что у меня после каждого хода ВСЁ поле банально обновлялось
Покажите код, где у вас после очередного хода обновляется массив c.

Но есть вероятность "потерять" где находится мина, если поставить два флажка: один на мину, а другой не на мину.
Совершенно верно. Если мы заменим мину флажком (доска то у нас теперь одна), то фактически мы изменили изначальное состояние игры. А проверять перед тем как поставить флажок - есть там мина или нет, и если нет - не ставить - противоречит правилам игры. Советую не смешивать данные (числовая доска) с выводом (символьная доска).

Теперь: действительно в данном виде данные (изначальное состояние доски) представлены наглядно но громоздко, с помощью примитивной структуры - двумерный массив. Насколько я понял, вы хотите оптимизировать представление данных задав их не с помощью числового массива, а с помощью списка координат мин. Это чревато тем что:

У нас потеряна индексация элементов. То есть: для ввода (x, y) раньше мы просто смотрели a[x][y], и эта операция просмотра была быстрой. Теперь мы должна будем найти этот (x, y) в списке {(x₀, y₀), (x₁, y₁), ... (x_k, y_k)} где k - кол-во бомб. Эта операция пробега по списку в худшем случае (вся доска заполнена бомбами и мы ищем последнюю) берёт больше времени и столько же памяти сколько и массив. Вопрос - что мы выиграли с такой структурой?

Если же вы хотите создать двумерный массив с координатами мин то то что я читаю это следующее:
a[0][0] = (bombXCoord0, bombYCoord0)
a[0][1] = (bombXCoord1, bombYCoord1)
...
a[k][l] = (bombXCoordt, bombYCoordt)

где t - кол-во бомб. Вопрос - зачем это делать? У нас нет никакой связи между координатами массива (k, l) и координатами бомбы в нём. А если и есть, то зачем нам пихать в (k, l) саму координату бомбы?

Таким образом, перед нами проблема растраты памяти (например для доски 100x100 где всего навсего 5 бомб - мы выделяем массив 100x100). Эффективное решение такой проблемы существует при более сложных структурах данных, но сначала вам необходимо освоить и приобрести навыки программирования и работы с самим языком (ставя и решая различные задачи).

[венди спенсер]

Насчет вывода. Вот такая ф-ия у меня для вывода ВСЕГО поля на экран. Я ф-ию Output вызываю после каждого действия (например: нажал на клавишу открытия клетки, клетка открылась [изменилось значение соответвующей ячейки], поле обновилось):

void Output()
{
for(int i=0;iА если и есть, то зачем нам пихать в (k, l) саму координату бомбы?
чтобы где-то "запомнить" координаты всех мин.

Эффективное решение такой проблемы существует при более сложных структурах данных, но сначала вам необходимо освоить и приобрести навыки программирования и работы с самим языком

хорошо, тогда откажусь от своих "гениальных" идей =)

[Слушатель]

хорошо, тогда откажусь от своих "гениальных" идей =)
Ни в коем случае этого не делайте. Это очень хорошо, что вы не остановились на достигнутом и продолжаете "крутить" проблему так и эдак. Такой "исcледовательский зуд" очень поможет вам в дальнейшем. Сам факт того, что вы вышли на проблему выше вашего уровня - это замечательно. Решение придёт - когда вы его достигнете.

[венди спенсер]

Решение придёт - когда вы его достигнете.

=)

Спасибо))