работа с массивом нулей и единиц

[Rusl92]

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

у нас есть массив 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
какой алгоритм в данном случае следует использовать?
заранее спасибо!

[LeBron]

БФС или ДФС на Ваш вкус. Запускать с каждой найденой неотмеченой единички.

[Скарам]

Хм...я попробовал обход...
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,это первое,и наверно надо сохранять предыдущий элемент(с которого мы ушли...).Чуть позже допишу.

[Rusl92]

а вообще эта задача на графы что ли?

[Rusl92]

некорректно работает

[Скарам]

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

[LeBron]

Задача старая, как мир. И до боли примитивная - никаких выдумок не надо, в одном знакомом мне лицее эту задачу 8класникам на 4 задавали, тоесть для проверки "полный ноль-не полный ноль". Объясняю более доступно и подробно. Заводим дополнительную матрицу для отмечения уже проверенных клеток. Проходим всю основную матрицу. Каждый раз, когда в основной матрице попадаем в клетку, которая в дополнительной еще не отмечена, а в основной содержит единицу, запускаем с нее БФС (если быть более точным - кажеться, эта вариация называеться "алгоритм Ли") и подсчитываем число клеток в связной области. Одновременно флагаем все пройденные клетки, что бы не проверять одну область несколько раз. Если в области больше клеток, чем текущий ответ, то ответом становиться количество клеток в области. Ответ после обхода - верный.

[Скарам]

Решил эту задачку влоб для матрицы 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;
}

[LeBron]

Сообщение от Скарам

Решил эту задачку влоб для матрицы 3х3 в принципе поменять матрицу и s(это размерность матрицы) и можно считать для любой.Смысл в том,что мы нашли 1 и пошли от неё на все 4 стороны,учитывая где мы находимся(в углу матрицы,середине,где-то с краю(всего 9 вариантов местонахождения)...нудно,но реально и понятно)).Знание crtl+c и ctrl+v спасает при написании такого алгоритма)))

А можно увидеть решение для 100*100? А то это мне даже страшно проверять

[Скарам]

А можно увидеть решение для 100*100? А то это мне даже страшно проверять

Ну для начала Вы мне вразумительную матрицу...))))..А во вторых код можно сократить,если каждый такой if упаковать в функцию

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

				  flag=true;
				}

,а pn и pm объявить глобально...конечно такой способ ресурсозатратен,но думается,что сработать должно...)...но запускать его на матрице 100*100 я тоже не хочу))))