Понедельник, 25 Ноября 2024, 19:00

Приветствую Вас Гость

[ Новые сообщения · Игроделы · Правила · Поиск ]
  • Страница 1 из 2
  • 1
  • 2
  • »
Посчитать прямоугольники на клеточном листе
vicu2010Дата: Вторник, 22 Января 2013, 23:16 | Сообщение # 1
Сейчас нет на сайте
Помогите решить, вопрос конечно разъеженный - но я в гугле на ответ не наткнулся. Был бы рад если-бы кто-нибудь мне объяснил как всё делается, я знаком с массивами и программирую вроде по чуть-чуть - хочу подготовится к олимпиаде.

Имеется квадратный клетчатый лист, на нем n*n клеток. Из нескольких клеток делаются прямоугольники, которые никогда не накладываются друг на друга. Прямоугольник может состоять даже из одной клетки. Они выделены цифрой 1, когда фон цифрой 0.

Цель: Посчитать Прямоугольники на листе.

К примеру: n=5

0 0 0 0 0
1 0 1 1 0
1 0 1 1 0
0 0 0 0 0
0 0 0 0 0

В данном случае у нас 2 прямоугольника в матрице.



Программист Ruby on Rails / COBOL | Веб-дизайнер(Bootstrap, HTML5, JS) | Викверс на Construct 2 / Classic


Сообщение отредактировал vicu2010 - Среда, 23 Января 2013, 20:01
justfolerДата: Вторник, 22 Января 2013, 23:41 | Сообщение # 2
почетный гость
Сейчас нет на сайте
Ты не можешь посчитать прямоугольники не зная их размера.
В твоем примере может существовать 25 одноклеточных прямоугольников или один прямоугольник 5*5
vicu2010Дата: Среда, 23 Января 2013, 15:11 | Сообщение # 3
Сейчас нет на сайте
Размер может быть любым. Так-же и размер карты может быть любым.

Добавлено (23.01.2013, 15:11)
---------------------------------------------
Пацаны помогите, реально надо. Надо за 2 дня выучить эти чёртовы алгоритмы, а понять их без помощи не могу.... тим круз, ты где?



Программист Ruby on Rails / COBOL | Веб-дизайнер(Bootstrap, HTML5, JS) | Викверс на Construct 2 / Classic
FaetonДата: Среда, 23 Января 2013, 16:02 | Сообщение # 4
частый гость
Сейчас нет на сайте
Полагаю что между прямоугольниками обязательно есть свободная клетка, тогда:
для каждой строки с первой и до последней перебираю клетки. Если вниз от текущей клетки (занятой) пусто или за пределами массива && вправо от клетки пусто или за пределами массива то +1 к количеству. Вот и весь алгоритм


Сообщение отредактировал Faeton - Среда, 23 Января 2013, 16:03
СибирскийДата: Среда, 23 Января 2013, 16:14 | Сообщение # 5
Javatar
Сейчас нет на сайте
Возможны пересечения?

firedayДата: Среда, 23 Января 2013, 20:13 | Сообщение # 6
частый гость
Сейчас нет на сайте
Переделываю

Сообщение отредактировал fireday - Среда, 23 Января 2013, 20:48
GECKДата: Среда, 23 Января 2013, 20:37 | Сообщение # 7
заслуженный участник
Сейчас нет на сайте
fireday, нашел случай, когда не работает:

Вот мой вариант. Громоздко, но считает вроде все. В файле input.txt первое число - это размер поля.


Всё гениальное просто. И хреново работает.
СибирскийДата: Среда, 23 Января 2013, 20:46 | Сообщение # 8
Javatar
Сейчас нет на сайте
GECK, ваш контрпример, мягко говоря, ниочем. Там, очевидно множество вариантов.
VBA - не язык


GECKДата: Среда, 23 Января 2013, 20:51 | Сообщение # 9
заслуженный участник
Сейчас нет на сайте
Цитата (Сибирский)
Там, очевидно множество вариантов.

Но во всех этих вариантах должно получиться больше двух прямоугольников. В этом-то и соль.


Всё гениальное просто. И хреново работает.
firedayДата: Среда, 23 Января 2013, 20:53 | Сообщение # 10
частый гость
Сейчас нет на сайте
Условие задачи полное?
Я так понимаю требуется найти минимально возможное количество прямоугольников?
Могут ли они соприкасаться?
СибирскийДата: Среда, 23 Января 2013, 20:57 | Сообщение # 11
Javatar
Сейчас нет на сайте
GECK, это не верный контрпример. Очевидно, что на нем неправильный ответ. Не аргумент

vicu2010Дата: Среда, 23 Января 2013, 21:00 | Сообщение # 12
Сейчас нет на сайте
GECK, Спасибо чел, работает, но это чертовски большая программа, я бы сказал уж слишком большая... И использовал ты обжект паскаль - не думаю, что на олимпиадах такое позволят((

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

Я пытаюсь сделать через алгоритм, типа если клетка равна 1 и клетка сверху и слева этой 0 - то прибавить к счётчику. Однако почему-то не работает. Вот код:
Код
program dreptunghi;
var a : array[1..3000,1..3000] of byte;  
     i,j,u,n:integer; inp:text;
begin
   Writeln('Introdu N:');
   readln(n); // колво колонок  
   assign(inp, 'inp.txt'); reset(inp); // тут грузим матрицу с тхтэщника
   for i:=1 to n do begin
    for j:=1 to n do read(inp, a[i,j]);
    readln(inp); end;
   for i:=1 to n do begin
    for j:=1 to n do write(a[i,j],' ');
    writeln; end;
   writeln;
    
   for i:=1 to n do  
    for j:=1 to n do
     if a[i,j]=1 then begin
      if (a[i-1,j]) and (a[i,j+1])=0 then u:=u+1;
      end;
     //собственно тут происходит проверка

   for i:=1 to n do begin
    for j:=1 to n do write(a[i,j],' ');
    writeln; end;
   Writeln(u);
   close(inp);
end.


Понять не могу почему не срабатывает, ещё подумаю - попробую решить.

Добавлено (23.01.2013, 21:00)
---------------------------------------------

Цитата (fireday)
Могут ли они соприкасаться?

нет



Программист Ruby on Rails / COBOL | Веб-дизайнер(Bootstrap, HTML5, JS) | Викверс на Construct 2 / Classic
firedayДата: Среда, 23 Января 2013, 21:05 | Сообщение # 13
частый гость
Сейчас нет на сайте
Цитата (vicu2010)
Цитата (fireday)
Могут ли они соприкасаться?

нет

ясно


Сообщение отредактировал fireday - Среда, 23 Января 2013, 21:07
СибирскийДата: Среда, 23 Января 2013, 21:07 | Сообщение # 14
Javatar
Сейчас нет на сайте
vicu2010, если олимпиада не лоховская какая-нибудь, сдаются задачи на тестировщик. Тогда возможность использования языка определяется компилятором.

vicu2010Дата: Среда, 23 Января 2013, 21:12 | Сообщение # 15
Сейчас нет на сайте
fireday, спасибо, работает и к тому-же всё просто и понятно)

Добавлено (23.01.2013, 21:12)
---------------------------------------------

Цитата (Сибирский)
vicu2010, если олимпиада не лоховская какая-нибудь, сдаются задачи на тестировщик. Тогда возможность использования языка определяется компилятором.

Не знаю, я в этом заведение первый год участвую... А так, то в колледже нас обычному паскалю обучают..



Программист Ruby on Rails / COBOL | Веб-дизайнер(Bootstrap, HTML5, JS) | Викверс на Construct 2 / Classic
СибирскийДата: Среда, 23 Января 2013, 21:14 | Сообщение # 16
Javatar
Сейчас нет на сайте
Я бы сделал аналог графа и определил количество компонент связности

firedayДата: Среда, 23 Января 2013, 21:23 | Сообщение # 17
частый гость
Сейчас нет на сайте
На языке паскаль
Код
program project1;  
var  
mass:array[1..100,1..100] of byte;  
i,j,n,m,val:byte;  
Check1,Check2:boolean;  
begin  
writeln('razmer massiva N*M');  
writeln('vvedite N');  
readln(n);  
writeln('vvedite M');  
readln(m);  
writeln('vvedite massiv ',n,'*',m);  
for i:=1 to n do  
for j:=1 to m do  
read(mass[i,j]);  
for i:=1 to n do  
for j:=1 to m do  
begin  
   if mass[i,j]=1 then  
   begin  
     Check1:=false;
     Check2:=false;
     if i=n then Check1:=true;  
     if i<n then if mass[i+1,j]=0 then Check1:=true;  
     if j=m then Check2:=true;  
     if j<m then if mass[i,j+1]=0 then Check2:=true;  
     if Check1=true and Check2=true then val:=val+1;  
   end;  
end;  
writeln('Otvet: ',val);  
readln;  
end.
GECKДата: Среда, 23 Января 2013, 21:43 | Сообщение # 18
заслуженный участник
Сейчас нет на сайте
Цитата (vicu2010)
т.е. всегда между прямоугольников будут нолики...

Ну так неинтересно smile В таком случае все верно - достаточно подсчитать количество углов.


Всё гениальное просто. И хреново работает.
vicu2010Дата: Среда, 23 Января 2013, 21:57 | Сообщение # 19
Сейчас нет на сайте
fireday, Не знаю что в твоём варианте с проверочником(check var), но всунув и его в мой алгоритм, он заработал:
Код
program dreptunghi;
var a : array[1..3000,1..3000] of byte;  
     i,j,u,n,m:integer; inp:text;
begin
   Writeln('Introdu N:');
   readln(n);
   assign(inp, 'inp.txt'); reset(inp);
   for i:=1 to n do begin
    for j:=1 to n do read(inp, a[i,j]);
    readln(inp); end;
   for i:=1 to n do begin
    for j:=1 to n do write(a[i,j],' ');
    writeln; end;
   writeln;

   for i:=1 to n do  
    for j:=1 to n do
     if a[i,j]=1 then begin
      u:=0;
      if (a[i-1,j])=0 then u:=u+1;  
      if (a[i,j+1])=0 then u:=u+1;
      if u=2 then m:=m+1;
     end;
   for i:=1 to n do begin
    for j:=1 to n do write(a[i,j],' ');
    writeln; end;
   Writeln(m);
   close(inp);
end.

Добавлено (23.01.2013, 21:57)
---------------------------------------------
GECK, ну да, я просто изучаю азы...



Программист Ruby on Rails / COBOL | Веб-дизайнер(Bootstrap, HTML5, JS) | Викверс на Construct 2 / Classic
firedayДата: Четверг, 24 Января 2013, 11:07 | Сообщение # 20
частый гость
Сейчас нет на сайте
Цитата (vicu2010)
я просто изучаю азы...
Все с этого начинали.
Удачного изучения.)
  • Страница 1 из 2
  • 1
  • 2
  • »
Поиск:

Все права сохранены. GcUp.ru © 2008-2024 Рейтинг