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

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

В общем коротко о сути проблемы:
Приспичило мне написать консольную версию Сапёра на 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

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

Ладно - отбой...
Сделал в обход проблемы. Через одно место правда, но уж как есть.

Вот плод моих трудов:
rghost.ru/2422242

[Слушатель]

Catch By Madness
Во-первых, вы выполняете за функцию rek её же работу. Рассмотрим следующие строки:
Вот эти:
1. c[y][x]=a[y][x]+48; //открываю текущую клетку.
2. if(c[y][x]=='0') // если она пустая, то выполняю следующее.

И например эту:
3. if(a[y-1][x]==0)

Мы видим, что строки 2 и 3 отличаются только названиями массивов, и значением индексов. Но ведь мы уже поставили в строке 2, похожую проверку? А строка 2 выполняется при вызове функции rek. Значит что нужно сделать, чтобы избежать повторного кода? Восемь раз вызвать проверку для соседей. Какая функция у нас ответственна за проверку клетки на пустоту? Функция rek. Таким образом:

If (a[x][y] = 0)
{
   …?
   …?
   …?
   …?
   …?
   …?
   …?
   …?
}

После этого внимательно проследите за ходом функции rek, чтобы понять что происходит.

Во-вторых функция rek должна вызываться только если мы нажали на пустую клетку. Иначе мы раскрываем сразу всё поле при рекурсивном обходе.

В-третьих в функции rek нет условия останова, и именно поэтому мы пытаемся доступиться до запрещённых индексов массива, и получаем в глаз от компилятора ).

В-четвёртых что самое главное, вы рискуете натолкнуться на следующую вещь:
допустим мы вызываем обход для клетки (1, 1). На каком-то этапе при рекурсивном обходе остальных клеток, мы опять придём в клетку (1, 1) проверим её на пустоту и опять пойдём обходить доску (зациклились). Как этого избежать?

Кроме того, пожалуйста давайте осмысленные имена переменным. Так например вместо a - origBoard, c - updatedBoard, rek - OpenEmptyCells и т.д. И не используйте глобальные переменные.

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

Спасибо)
Да - недочеты заметил.

насчет имен переменных - спасибо) буду применять=)

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

теперь такая вот колбаса:
это реккурентная ф-ия, для открытия любой клетки с проверкой на пустую клетку:

void click(int x, int y)
{
if(x<1 || x>n || y<1 || y>m) // это чтобы за границы поля не выходил.
return; //(*)

if(a[x][y]==0) //проверка на пустую клетку.(*)
{//(*)
click(x-1,y-1);//(*) и так далее...
click(x,y-1);
click(x+1,y-1);
click(x-1,y);
click(x+1,y);
click(x-1,y+1);
click(x,y+1);
click(x+1,y+1);
return;
}

if(a[x][y]==9)
{
cout << "You dead";
getch();
exit(0);
}

c[x][y]=a[x][y]+48; //это открытие поля.
}

вызывается вот так:

if(f=='x')
{
click(y,x);

gotoxy(1,1);
Output();
gotoxy(x,y);
}

то есть все действия в ф-ии.

Но так тоже ПОЧЕМУ-ТО не работает.
вот такая вот ошибка при компилляции: Illegal character ' ' (0xa0)
в строчках, что я пометил (*).

Теперь я окончательно повис(

[Слушатель]

вот такая вот ошибка при компилляции: Illegal character ' ' (0xa0)
скорее всего доска c изначально следующего вида:
c = {‘’, ‘’, …’’
‘’, ‘’, … ‘’
…
‘’, ‘’, …, ‘’}
Замените символ ‘’ на например ‘x’ (нераскрытая клетка).

Кроме этого небольшого недочёта в вашей программе имеются следующие серьёзные ошибки:
1. Игрок нажав на пустую клетку может получить сообщение «you dead»
2. Для определённого ввода, программа может войти в бесконечную рекурсию.
3. При нажатии на пустую клетку на выводе может распечататься вся открытая доска (вариант ошибки 1).

Рассмотрим их подробнее:
1. Зададим доску 3х3 следующего вида:
a = {9, 0, 1
0, 0, 0
0, 0, 0}
Допустим вызов click(1, 1). Функция видит пустую клетку, рекурсивно запускает click(0, 0). Для вызова click(0, 0) получается a[0][0] == 9, выдаётся сообщение «You dead».

2. Про этот пункт я объяснял в предыдущем своём сообщении.
Зададим доску вида:
a = {0, 0, 0
0, 0, 0
0, 0, 0}

Допустим вызов click(1, 1). Рассмотрим последовательность вызовов:

(1) click(1, 1) = (2) click(0, 0) = (3) click(-1, -1) {return to (2)} = (4) click(0, -1) {return to (2)} = (5) click(1, -1) {return to (2)}
= (6) click(-1, 0) {return to (2)} = (7) click(1, 0) = (8) click(0, -1) {return to (7)} = click(1, -1) {return to (7)}
= click(2, -1) {return to (7)} = click(0, 0) а это опять шаг (2). Зациклились.

3. Это вариант 1-й ошибки, только вместо второго if-a выполняется строка:
c[x][y]=a[x][y]+48;

и когда матрица c подастся на выход в ней будут «раскрыты» клетки которых игрок не раскрывал. Например:

a = {1, 0, 0
9, 0, 0
0, 0, 0}

Допустим вызов click(1, 1). Функция видит пустую клетку, рекурсивно запускает click(0, 0). Для вызова click(0, 0) получается a[0][0] == 1, значит c[0][0] = ‘1’. Зря раскрыли игроку клетку.

Подумайте, как можно исправить эти ошибки. Советую, чтобы функция click запускалась не в любом случае, а только если в main-е мы натолкнулись на пустую клетку. Иначе у вас нарушается принцип разделения работы (все действия в одной функции), и в частности это приводит к таким ошибкам.

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

Слушатель, спасибо еще раз ВОООТ ТАКОЕ.

Буду продолжать полировать.

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

Слушатель
меня посетил такой вопрос: вот все примеры "заданных досок".
они же нереальны в игре.
9 - это же мина.

То есть в 1 доска будет:
9 1 0
1 1 0
0 0 0

проблема вида 2 правда остается...

[Слушатель]

Catch By Madness
Да верно, для любой клетки (i, j) если там мина то в клетках её огороживающих пустых нет, и значит для любого пустого хода мы рекурсивно наткнёмся на одну из огораживающих клеток и зря скопируем цифру (проблема 3). Можно доказать это построже, но не требуется.

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

Слушатель
ну в оригинале игры вроде как пустые поля открываются вплоть до непустых ВКЛЮЧИТЕЛЬНО...

[Слушатель]

Catch By Madness
"Это не баг, а фича" .

Тогда осталась только проблема 2.

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

"Это не баг, а фича" .

=)))

Да - но вторая проблема - это проблема... да...

[Слушатель]

Catch By Madness
Подсказать, или сами?

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

Разрываюсь...
ммм...

а если не подсказать, а намекнуть?..

[Слушатель]

Catch By Madness
Представьте себе, что вы стоите на круглой площадке по периметру которой стоят столбы. Вам надо их сосчитать, но у вас очень плохая память и вы не можете запомнить от какого столба вы перешли, в результате вы будете вертеться по круглой площадке до бесконечности. Как этого избежать? Стройте любую версию.

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

пока для алгоритма ничего не приходит. Нужна отправная точка, например...

[Слушатель]

Catch By Madness
Нужна отправная точка, например...

Верное направление. Ну пусть отправной точкой у нас будет крестик нарисованный мелом на столбе. Дальше?

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

ну если круглая площадка, то я просто по очереди все обхожу, до того, пока не дойду до столба с крестиком...

[Слушатель]

Catch By Madness
Отлично. Теперь рассмотрим функцию click. При каком условии мы начинаем её рекурсивно вызывать (начинать обходить столбы)?

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

Ну, вот когда она в таком виде:

void click(int x, int y)
{
if(x<1 || x>n || y<1 || y>m) // это чтобы за границы поля не выходил.
return; //(*)

if(a[x][y]==0) //проверка на пустую клетку.(*)
{//(*)
click(x-1,y-1);//(*) и так далее...
click(x,y-1);
click(x+1,y-1);
click(x-1,y);
click(x+1,y);
click(x-1,y+1);
click(x,y+1);
click(x+1,y+1);
return;
}

c[x][y]=a[x][y]+48; //это открытие поля.
}

То вызываем мы ее для открытия клетки... То есть... У меня - по нажатии клавиши "Х" на клавиатуре...

if(f=='x')
{
click(y,x);

gotoxy(1,1);
Output();
gotoxy(x,y);
}

[Слушатель]

Catch By Madness
То вызываем мы ее для открытия клетки....

В main-е мы действительно её вызываем если f == 'x'. В самой же функции мы её вызываем если a[x][y] == 0.
Вот допустим мы открыли пустую клетку c координатами (i, j), пошли обходить, обходить... и на определённом этапе опять наткнулись на ту же пустую клетку (с координатами (i, j)) (пришли к тому же столбу от которого вышли). Как этого избежать?

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

запомнить в переменную (две) координаты начала обхода?

[Слушатель]

Catch By Madness
Мысль интересная но неудобная. Нам придётся:

1. Передать функции click в самом начале "болванки" вместо координат.
2. Каждый раз передавать эти координаты при вызове. В итоге получим, что функция click ждёт уже 4 параметра: x, y, emptyX, emptyY. Некрасиво.

Следующая версия?

UPD: немного подправил своё предыдущее сообщение.

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

я чуток застрял...

с учетом:
"2. Каждый раз передавать эти координаты при вызове. В итоге получим, что функция click ждёт уже 4 параметра: x, y, emptyX, emptyY."
записывать все пройденные пустые клетки в массив еще некрасивее...

Так...

то есть цель - это не попадать дважды на одну и ту же пустую клетку - я правильно понял?


нужно время.
я подумаю...

[Слушатель]

Catch By Madness
то есть цель - это не попадать дважды на одну и ту же пустую клетку - я правильно понял?

Не совсем. Цель - это чтобы проверка if (a[x][y] == 0) не сработала на той же клетке 2-й раз.

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

"Не совсем. Цель - это чтобы проверка if (a[x][y] == 0) не сработала на той же клетке 2-й раз."

хорошо, тогда после того как мы вошли в условие if (a[x][y] == 0)
сразу задать другое значение для a[x][y] ... например:

if(a[x][y]==0)
{

a[x][y]=-1;

click(x-1,y-1);
click(x,y-1);
click(x+1,y-1);
...

поможет?

[Слушатель]

Catch By Madness
Мы почти у цели.

Теперь функция не циклится, но будет выполняться c[x][y]=a[x][y]+48; //это открытие поля. Нам нужно чтобы функция увидев "крестик" - возвращалась бы из своего вызова. Как это сделать?

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

может так?

if(a[x][y]==0)
{

a[x][y]=-1;

click(x-1,y-1);
click(x,y-1);
click(x+1,y-1);
...


...

if(a[x][y]==-1)
break;
// или return?
хотя нет. брейк...

[Слушатель]

Catch By Madness
break - мы выходим из текущего блока инструкций и переходим на следующую строку.
return - возвращаемся из вызова в предыдущий вызов и выполняем следующую инструкцию.

Что нам нужно? По сути a[x][y] == -1 это еще один вид условия останова то есть как if(x<1 || x>n || y<1 || y>m).

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

а ну точно... мы же ведь не в условие вернуться должны, а на шаг назад в рекурсии вернуться..

Тогда в итоге получилось как-то так:

void click(int x, int y)
{
if(x<1 || x>n || y<1 || y>m) // это чтобы за границы поля не выходил.
return; //(*)

if(a[x][y]==0) //проверка на пустую клетку.(*)
{

a[x][y]=-1;

click(x-1,y-1);//(*) и так далее...
click(x,y-1);
click(x+1,y-1);
click(x-1,y);
click(x+1,y);
click(x-1,y+1);
click(x,y+1);
click(x+1,y+1);
return;
}

if(a[x][y]==-1)
return;

c[x][y]=a[x][y]+48; //это открытие поля.
}

вот как-то так?

[Слушатель]

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

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