Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 15.11.2009, 12:19   #1
Rusl92
Форумчанин
 
Аватар для Rusl92
 
Регистрация: 30.03.2008
Сообщений: 392
Плохо работа с массивом нулей и единиц

здравствуйте не могли бы вы мне подсказать, как решать такую задачу

у нас есть массив NxN который заполнен нулями и единицами

нужно найти максимальное количество единиц, которые "соединены"


Код:
1 0 0 0 0
0 1 0 0 1
0 1 0 1 1
1 1 0 0 0
0 0 0 0 1
в данном случае ответ будет 4
какой алгоритм в данном случае следует использовать?
заранее спасибо!
Программирование - это великое искусство... Такое же как например и живопись!
Rusl92 вне форума Ответить с цитированием
Старый 15.11.2009, 12:28   #2
LeBron
Форумчанин
 
Регистрация: 10.10.2009
Сообщений: 680
По умолчанию

БФС или ДФС на Ваш вкус. Запускать с каждой найденой неотмеченой единички.
LeBron вне форума Ответить с цитированием
Старый 15.11.2009, 12:37   #3
Скарам
Дружите с Linq ;)
Форумчанин
 
Аватар для Скарам
 
Регистрация: 15.10.2008
Сообщений: 822
По умолчанию

Хм...я попробовал обход...
1)Бежим по массиву,пока не наткнемся на 1(по строкам,допустим).
2)Запускаем
Код:
maxkolvo=0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
bool flag=true;

n=i;m=j;kolvo=0;
if mas[i][j]==1)
{
while(flag==true)
{ if(mas[n][m+1]==1)
    {
       m++;kolvo++;
     }
   if(mas[n+1][m]==1)
       {
       n++;kolvo++;
     }
     if(mas[n-1][m]==1)
   {
       n--;kolvo++;
     }
    if(mas[n][m-1]==1)
       {
       m--;kolvo++;
      }
   else flag=false;
}
if(kolvo>maxkolvo)maxkolvo=kolvo;
}
}
Писал прям в окне сообщения,поэтому могут быть недочеты...в принципе алгоритм неидеальный и требует доработки,но если таким образом пробежать матрицу,то можно все варианты этих змей перебрать и выявить длиннейшую..))
Не корректно работает,потому что на проверять равны в while равны ли i и j 0,это первое,и наверно надо сохранять предыдущий элемент(с которого мы ушли...).Чуть позже допишу.
Не давай организму поблажки, каждый день тренируй его в шашки..

Последний раз редактировалось Скарам; 15.11.2009 в 13:01.
Скарам вне форума Ответить с цитированием
Старый 15.11.2009, 12:37   #4
Rusl92
Форумчанин
 
Аватар для Rusl92
 
Регистрация: 30.03.2008
Сообщений: 392
По умолчанию

а вообще эта задача на графы что ли?
Программирование - это великое искусство... Такое же как например и живопись!
Rusl92 вне форума Ответить с цитированием
Старый 15.11.2009, 12:58   #5
Rusl92
Форумчанин
 
Аватар для Rusl92
 
Регистрация: 30.03.2008
Сообщений: 392
По умолчанию

некорректно работает
Программирование - это великое искусство... Такое же как например и живопись!
Rusl92 вне форума Ответить с цитированием
Старый 15.11.2009, 12:58   #6
Скарам
Дружите с Linq ;)
Форумчанин
 
Аватар для Скарам
 
Регистрация: 15.10.2008
Сообщений: 822
По умолчанию

Ну вообще это работа с матрицами скорее всего,на матрицу смежностей однонаправленного графа похоже,но таких задач на них я не встречал.
Не давай организму поблажки, каждый день тренируй его в шашки..
Скарам вне форума Ответить с цитированием
Старый 15.11.2009, 14:03   #7
LeBron
Форумчанин
 
Регистрация: 10.10.2009
Сообщений: 680
По умолчанию

Задача старая, как мир. И до боли примитивная - никаких выдумок не надо, в одном знакомом мне лицее эту задачу 8класникам на 4 задавали, тоесть для проверки "полный ноль-не полный ноль". Объясняю более доступно и подробно. Заводим дополнительную матрицу для отмечения уже проверенных клеток. Проходим всю основную матрицу. Каждый раз, когда в основной матрице попадаем в клетку, которая в дополнительной еще не отмечена, а в основной содержит единицу, запускаем с нее БФС (если быть более точным - кажеться, эта вариация называеться "алгоритм Ли") и подсчитываем число клеток в связной области. Одновременно флагаем все пройденные клетки, что бы не проверять одну область несколько раз. Если в области больше клеток, чем текущий ответ, то ответом становиться количество клеток в области. Ответ после обхода - верный.
LeBron вне форума Ответить с цитированием
Старый 15.11.2009, 14:28   #8
Скарам
Дружите с Linq ;)
Форумчанин
 
Аватар для Скарам
 
Регистрация: 15.10.2008
Сообщений: 822
По умолчанию

Решил эту задачку влоб для матрицы 3х3 в принципе поменять матрицу и s(это размерность матрицы) и можно считать для любой.Смысл в том,что мы нашли 1 и пошли от неё на все 4 стороны,учитывая где мы находимся(в углу матрицы,середине,где-то с краю(всего 9 вариантов местонахождения)...нудно,но реально и понятно)).Знание crtl+c и ctrl+v спасает при написании такого алгоритма)))
Код:
#include <iostream>
using namespace std;
//---------------------------------------------------------------------------
 int mas[3][3]={0,1,0,1,1,0,1,0,1};
#pragma argsused
int main(int argc, char* argv[])
{
int maxkolvo=0,kolvo;int n,m,pn=0,pm=0;
int s=3;//матрица sxs
for(int i=0;i<s;i++)
{
	for(int j=0;j<s;j++)
		{
			bool flag=true;

			n=i;m=j;kolvo=1;
			if (mas[i][j]==1)
			{
			  while(flag==true)
			  {
				flag=false;
				if(n!=0 && m!=0 && n!=(s-1) && m!=(s-1))
				{
				if(mas[n][m+1]==1 && (m+1)!=pm )
						{
							pm=m;pn=n;
							 m++;kolvo++;
							 flag=true;
						}
				 if(mas[n+1][m]==1 && (n+1)!=pn )
						{
							pm=m;pn=n;
							 n++;kolvo++;
							 flag=true;
						}
				 if(mas[n-1][m]==1&& (n-1)!=pn )
						{   pm=m;pn=n;
							n--;kolvo++;

							flag=true;
						}
				 if(mas[n][m-1]==1 && (m-1)!=pm)
						{   pm=m;pn=n;
							m--;kolvo++;
							
							flag=true;
						}

				 }
				if(n==0 && m==0)
					{
						if(mas[n][m+1]==1 &&(m+1)!=pm )
						{    pm=m;pn=n;
							 m++;kolvo++;
							 
							 flag=true;
						}
				 if(mas[n+1][m]==1 && (n+1)!=pn )
						{    pm=m;pn=n;
							 n++;kolvo++;
							 
							 flag=true;
						}

					}
				 if(n==0 && m==(s-1))
					{
						 if(mas[n][m-1]==1 &&(m-1)!=pm)
						{   pm=m;pn=n;
							m--;kolvo++;
							
							flag=true;
						}
						 if(mas[n+1][m]==1 && (n+1)!=pn)
						{    pm=m;pn=n;
							 n++;kolvo++;

							 flag=true;
						}

					}
					if(n==(s-1) && m==0)
					{
						if(mas[n-1][m]==1&& (n-1)!=pn )
						{   	pm=m;pn=n;
							n--;kolvo++;

							flag=true;
						}
						if(mas[n][m+1]==1 &&(m+1)!=pm )
						{    pm=m;pn=n;
							 m++;kolvo++;
							 
							 flag=true;
						}

					}
					if(n==(s-1)&& m==(s-1))
						{
							 if(mas[n-1][m]==1&& (n-1)!=pn )
							{ pm=m;pn=n;
							n--;kolvo++;
							
							flag=true;
							}
							if(mas[n][m-1]==1 &&(m-1)!=pm)
							{   pm=m;pn=n;
							m--;kolvo++;
							
							flag=true;
							}

						}
					if(m==0)
					{
							if(mas[n][m+1]==1  &&(m+1)!=pm )
						{    pm=m;pn=n;
							 m++;kolvo++;
							 
							 flag=true;
						}
						if(mas[n+1][m]==1 && (n+1)!=pn )
						{    pm=m;pn=n;
							 n++;kolvo++;
							 
							 flag=true;
						}
						if(mas[n-1][m]==1&& (n-1)!=pn )
						{   pm=m;pn=n;
							n--;kolvo++;
							
							flag=true;
						}

					}
					if(n==0)
						{
							 if(mas[n][m+1]==1 &&(m+1)!=pm )
							{pm=m;pn=n;
							 m++;kolvo++;
							 
							 flag=true;
							}
							if(mas[n+1][m]==1 && (n+1)!=pn )
							{
							 pm=m;pn=n;
							 n++;kolvo++;
							  
							  flag=true;

							}
							if(mas[n][m-1]==1  &&(m-1)!=pm)
							{  pm=m;pn=n;
							m--;kolvo++;

							flag=true;
							}

						}
					 if(m==(s-1))
					{
							if(mas[n][m-1]==1  &&(m-1)!=pm )
						{    pm=m;pn=n;
							 m--;kolvo++;
							 
							 flag=true;
						}
						if(mas[n+1][m]==1 && (n+1)!=pn )
						{
							 pm=m;pn=n;n++;kolvo++;

							 flag=true;
						}
						if(mas[n-1][m]==1&& (n-1)!=pn )
						{   pm=m;pn=n;
							n--;kolvo++;
							
							flag=true;
						}

					}
					if(n==(s-1))
						{
							 if(mas[n][m+1]==1 &&(m+1)!=pm )
							{ pm=m;pn=n;
							 m++;kolvo++;

							 flag=true;
							}
							if(mas[n-1][m]==1 && (n-1)!=pn )
							{ pm=m;pn=n;
							 n--;kolvo++;
							 
							 flag=true;
							}
							if(mas[n][m-1]==1 &&(m-1)!=pm)
							{ pm=m;pn=n;
							m--;kolvo++;

							flag=true;
							}

						}
				   if(kolvo>maxkolvo)maxkolvo=kolvo;
			   }

			}
		  
		}
 }

 cout<<maxkolvo;
 getchar();
	return 0;
}
Не давай организму поблажки, каждый день тренируй его в шашки..
Скарам вне форума Ответить с цитированием
Старый 15.11.2009, 14:40   #9
LeBron
Форумчанин
 
Регистрация: 10.10.2009
Сообщений: 680
По умолчанию

Цитата:
Сообщение от Скарам Посмотреть сообщение
Решил эту задачку влоб для матрицы 3х3 в принципе поменять матрицу и s(это размерность матрицы) и можно считать для любой.Смысл в том,что мы нашли 1 и пошли от неё на все 4 стороны,учитывая где мы находимся(в углу матрицы,середине,где-то с краю(всего 9 вариантов местонахождения)...нудно,но реально и понятно)).Знание crtl+c и ctrl+v спасает при написании такого алгоритма)))
А можно увидеть решение для 100*100? А то это мне даже страшно проверять
LeBron вне форума Ответить с цитированием
Старый 15.11.2009, 14:53   #10
Скарам
Дружите с Linq ;)
Форумчанин
 
Аватар для Скарам
 
Регистрация: 15.10.2008
Сообщений: 822
По умолчанию

Цитата:
А можно увидеть решение для 100*100? А то это мне даже страшно проверять
Ну для начала Вы мне вразумительную матрицу...))))..А во вторых код можно сократить,если каждый такой if упаковать в функцию
Код:
              if(mas[n][m+1]==1 &&(m+1)!=pm )
				{ pm=m;pn=n;
				   m++;kolvo++;

				  flag=true;
				}
,а pn и pm объявить глобально...конечно такой способ ресурсозатратен,но думается,что сработать должно...)...но запускать его на матрице 100*100 я тоже не хочу))))
Не давай организму поблажки, каждый день тренируй его в шашки..
Скарам вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Работа с массивом GaSST Microsoft Office Excel 5 04.06.2009 07:57
Найти максимальный элемент матрицы и вставить правее него столбец из нулей и ниже него строку из нулей. Romer9999 Паскаль, Turbo Pascal, PascalABC.NET 3 28.11.2008 11:28
Получите последовательность b1...bn из нулей и единиц Я_Студент Паскаль, Turbo Pascal, PascalABC.NET 2 04.07.2008 12:40
работа с массивом begemotikdin Паскаль, Turbo Pascal, PascalABC.NET 2 21.06.2008 21:40