Здравствуйте! Прошу помощь,
на экзамене дали вот такую задачу:
есть двумерный массив заполненный нулями
и единицами нужно найти сколько есть
пятен в этом массиве и какой длины каждое пятно.
Пятно состоит из единичек которые находятся
в соседних клеткох, например:
1 0 0 1 0 0
0 0 1 1 1 0
1 0 0 0 0 1
1 1 0 0 1 0
ответ: есть 3 пятна длиной: 1 3 6
код C++. Заранее благодарен!

А что подразумевается под помощью? Все сделать вместо тебя? Это не помощь.
Помести свой вариант кода и тебе помогут и подскажут, а так это не правильно!
Что мне тут интересно, а размерность массива задана или как? И, потом, по-моему, ответ и картинка, по меньшей мере, не совпадают или я чего-то не понимаю.

Это сообщение отредактировал(а) brb - 16.2.2003, 02:54

раз ты знаешь код с++. то просто раскладываешь свои размышления по поиску пятен на мелкие этапы и программируешь их. так, например,
1. Поиск 1 единицы,
2. Поиск единиц рядом, если да то увеличить счетчик и прейти на найденную и т.д.,
....
....
...

здесь, определенно, рекурсия, с учетом просмотренного

Это сообщение отредактировал(а) Step - 16.2.2003, 18:27

грамматика:

Цитата

здесь определенно ...

Цитата

раз ты знаешь код с++. то просто раскладываешь свои размышления по поиску пятен на мелкие этапы и программируешь их. так, например, 1. Поиск 1 единицы, 2. Поиск единиц рядом, если да то увеличить счетчик и прейти на найденную и т.д., .... .... ... Здесь,определенно,рекурсия, с учетом просмотренного

Анатолий. с уважением относитесь к русскому языку!!! Глаза режет!

какая рекурсия?
цикл, ищем первую единицу - уходим в подпрограммку определения пятна, причем метим единицы из этого пятна.
выходим в цикл - ищем следующую непомеченую 1 и все.

Рекусия, все верно. Только вот клиент не определил что является соседними единицами, только горизонталь, или вертикаль тоже? или их считать отдельными "пятнами"? К тому же как уже отмечалось ответ и пример у него не совпадают.
1.3.6.
1 -просто не может быть.

Цитата

какая рекурсия? цикл, ищем первую единицу - уходим в подпрограммку определения пятна, причем метим единицы из этого пятна. выходим в цикл - ищем следующую непомеченую 1 и все.

можно и так

Algoritm Dii'kstra mojno primenit'. Predstav', chto edinicy - polja po kotorym mojno hodit', a nuli - prepjatstsvija. Dalee, kogda sovershaetsja shag, rekursivnaja funkcija uvelichivaet schetchik i peredaet ego na sledujuxhii' shag, esli konechno, on suxhestvuet.

Рекурсия здесь не нужна. Обходим массив волной.
Общий цикл, до тех пор, пока есть, что искать.
Ищем единицу, за нее "цепляемся" (присваиваем 2), просматриваем, все единицы, что рядом с 2 помечаем числом 2.
Нашли.
Увеличили счетчик.
Теперь, ежели находим единицу, то присваиваем ей 3 - далее - аналогично.
Без рекурсии, сложность N^3
ЗЫ
Рекурсия может не прокатить, пример - таблица NxN, где N<=1000.
Волной она быстро решается, а рекурсия в частных случаях вызовет переполнение стека.

Цитата

Рекурсия здесь не нужна. Обходим массив волной.

странно волну я всегда через рекурсию делал.
только надо начать волну с 0 и в зависимости сколько будет тупиков волны расчитать количество пятен
или начинать с найденной единици тогда и количество элементов пятна будет известно.

Цитата

Волной она быстро решается, а рекурсия в частных случаях вызовет переполнение стека.

ну это смотря по какому принцыпу запускать волну, в глубину или в ширину.

Alex101Кстати, как ты волну без рекурсии запускаеш. Я себе, конечно, такое представить могу, но это же абсурд.

Это сообщение отредактировал(а) Step - 17.2.2003, 01:16

Цитата

Кстати, как ты волну без рекурсии запускаешь.

С уважением, Алексей, пожалуйста, относитесь к родному языку. По-крайней мере, запомните правило написания глаголов во втором лице единственном числе - ВСЕГДА на конце мягкий знак. ВСЕГДА! Для справки - второе лицо это когда вы к кому-то обращаетесь, например, я к Вам, понимаешь?
Что такое: на конце, мякгий знак и единственное лицо прошу помощи форума для объяснения.

brb да я уже понял, только еще в привычку не вошло. И вообще - русский для меня не родной.

Цитата(Step @ 16.2.2003, 22:15)

Кстати, как ты волну без рекурсии запускаешь. Я себе, конечно, такое представить могу, но это же абсурд.

Просмотром всего массива. И никакой это не абсурд. Абсурдом было бы в приведенном мной ограничении для исходных данных делать рекурсию. Это не просто абсурд, а работать не всегда будет.

Цитата

Просмотром всего массива.

ну, у каждого свои подходы

Спасибо за отклики, соседи единицы такие: left, right, up, down,
right-up, right-down, left-up, left-down. Я понимаю вы здесь все крутые,
а ссылки на алгоритмы не даете. Если бы я знал код, то к Вам бы не
обращался. Но все равно спасибо за реакцию!

А вот функция которая не работает так как надо, rezult[] ето глобальный
массив в который записывается результат. L это следующий ход,
x_ , y_ позиция клетки.

void find(int L,int x_, int y_)
{
//L = x_ + y_;
result[x_ + y_] = L;

if(L == ROWS*COLS) exit(0);

if(arr[x_ + 1][y_] == 1)
{
find(L + 1,x_ + 1,y_); //right
}
else if (arr[x_ + 1][y_] == 0) find(L,x_+1,y_);

if(arr[x_ - 1][y_] == 1)
{
find(L + 1,x_ - 1,y_); //left
}
else if (arr[x_ - 1][y_] == 0) find(L,x_ - 1,y_);

if(arr[x_][y_ + 1] == 1)
{
find(L + 1,x_,y_ + 1); //up
}
else if(arr[x_][y_ + 1] == 0) find(L,x_,y_ + 1);

if(arr[x_][y_ - 1] == 1)
{
find(L + 1,x_,y_ - 1); //down
}
else if(arr[x_][y_ - 1] == 0) find(L,x_,y_ - 1);

if(arr[x_ + 1][y_ + 1] == 1)
{
find(L + 1,x_ + 1,y_ + 1);//right - up
}
else if(arr[x_ + 1][y_ + 1] == 0) find(L,x_ + 1,y_ + 1);

if(arr[x_ + 1][y_ - 1] == 1)
{
find(L + 1,x_ + 1,y_ - 1);//rihgt-down
}
else if(arr[x_ + 1][y_ - 1] == 0) find(L,x_ + 1,y_ - 1);

if(arr[x_ - 1][y_ + 1] == 1)
{
find(L + 1,x_ - 1,y_ + 1);//left-up
}
else if(arr[x_ - 1][y_ + 1] == 0) find(L,x_ - 1,y_ + 1);

if(arr[x_ - 1][y_ - 1] == 1)
{
find(L + 1,x_ - 1,y_ - 1);//left-down
}
else if(arr[x_ - 1][y_ - 1] == 0) find(L,x_ - 1,y_ - 1);
}

Все же решил с рекурсией?
Первый вопрос: Пятном считается совокупность клеток не только по горизонтали-вертикали, но и по диагонали? Ежели так, то ругательств по поводу диагоналей не будет

Код

if (arr[x_ + 1][y_] == 0) find(L,x_+1,y_);

А это для чего? (Это только один из твоих вариантов)
Для чего искать дальше, ежели уже ничего не нашли?
Ищем дальше в случае ненулевой клетки.
Или ты просто дальше ищешь следующие пятна? Тогда снова надо просматривать таблицу, перед этим найденное пятно должно быть удалено.

А вообще, по поводу готовых программ на форуме уже говорили. Здесь скажут, что именно у тебя неправильно или натолкнут на идею.
А написать готовое решение - это уже в разделе "Работа". (Ну или кому совсем нечего делать)
2 Step

Цитата

ну, у каждого свои подходы

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

Это сообщение отредактировал(а) Alex101 - 17.2.2003, 08:00