Посчитать прямоугольники на клеточном листе
| |
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) т.е. всегда между прямоугольников будут нолики... Ну так неинтересно В таком случае все верно - достаточно подсчитать количество углов.
Всё гениальное просто. И хреново работает.
|
|
| |
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) я просто изучаю азы... Все с этого начинали. Удачного изучения.)
|
|
| |
|