Visual Basic, .NET, ASP, VBScript
 

   
   
     

Форум - Олимпиады

Страница: 1 |

 

  Вопрос: Помогите кто-нибудь! Хитрая задачка! Добавлено: 16.10.06 15:42  

Автор вопроса:  virus
Друг предложил мне написать код под одну программу. Смысл ее таков:

"Получил я вчера задание нарисовать картинку размером H на W пикселей, обертку для конфет "Сосиска в шоколаде". Творчество – процесс тонкий, вдохновение требуется. А тут – как топором отрубило, ничего не выходит… От безысходности я нарисовал на белом экране красную замкнутую линию, толщиной в один пиксель. Сколько пикселей оказалось в области, ограниченной красной линией?"

Ограничения:

1<H,W<=100

Каждый красный пиксель имеет общие стороны ровно с двумя красными пикселями.

Ввод/вывод:

Программа должна прочитать с клавиатуры: с первой строки – два числа H и W, а со следующих H строчек по W чисел. Красный пиксель обозначается единицей, белый – нулем.

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

Пример:

Ввод> 5 7

Ввод> 0 0 0 1 1 1 0

Ввод> 0 1 1 1 0 1 0

Ввод> 0 1 0 0 0 1 0

Ввод> 0 1 1 1 1 1 0

Ввод> 0 0 0 0 0 0 0

Вывод> 4

Вообще данная задача должна решаться на Паскале, но т.к. я не особо умею с ним работать, то решил сделать ее
на VB.

Мне эта задача не нужна, но когда я столкнулся с ней и не смог решить ее, это стало делом принципа.

Если найдется добрый человек - пусть
пишет на мыло: dimon.fox@list.ru

Ответить

  Ответы Всего ответов: 14  

Номер ответа: 1
Автор ответа:
 Sharp


Лидер форума

ICQ: 216865379 

Вопросов: 106
Ответов: 9979
 Web-сайт: sharpc.livejournal.com
 Профиль | | #1
Добавлено: 16.10.06 16:43
Увеличиваешь поле с каждой стороны на 1 пиксель, заливаешь волновым алгоритмом, начиная с верхнего левого угла, искомая величина - площадь нового поля минус число залитых ячеек, минус число единиц.

Ответить

Номер ответа: 2
Автор ответа:
 vito



Разработчик Offline Client

Вопросов: 23
Ответов: 879
 Web-сайт: softvito.narod2.ru
 Профиль | | #2
Добавлено: 16.10.06 19:31
Можно так -же методом Монте-Карло подсчитать.

Ответить

Номер ответа: 3
Автор ответа:
 vito



Разработчик Offline Client

Вопросов: 23
Ответов: 879
 Web-сайт: softvito.narod2.ru
 Профиль | | #3
Добавлено: 17.10.06 03:15
Вот простой примерчик метода Монте-Карло.
Для того чтобы уловить суть, достаточно.

#include "stdafx.h"
#include "math.h"
#include <time.h>

int _tmain(int argc, _TCHAR* argv[];)
{
srand  ;(time (0)) ;

int arr[5][7]={
0, 0, 0, 1, 1, 1, 0,
0, 1, 1, 1, 0, 1, 0,
0, 1, 0, 0, 0, 0, 1,
0, 1, 1, 0, 1, 1, 0,
0, 0, 0, 1, 0, 0, 0};// немного модифицированная кривая (6 пикселей внутри)

int  count=0, count1=0;// счетчики
int rx,ry; // координаты (индексы массива)
for (int i=0;i<10000;i++) // нечинаем итерации (чем больше - тем точнее результат)
{
rx=rand()%10;// генерим два случайных числа
ry=rand()%10;
if (ry<5 && rx<7)// попали в квалрат?
{
count++;
if ((rx==1&& ry==4)||(rx==2&& ry==2)||(rx==2&& ry==3)||(rx==2&& ry==4)||(rx==3&& ry==3)||(rx==5&& ry==2)) // лениво было писать нормально

(сделаешь если захочещь сам:))
// проверяем попадание в ограниченную линией фигуру
count1++; // наращиваем счетчик


}
}


double pl =(double) count1/(double)count;// вычсляем отношение (попавших- не попавших)
double pl1 =(5*7)*pl; // вычисляем площадь (кол-во пикселей)

printf( "Number pixel= %4.0f\n", pl1 ); // выводим = 6

return 0;
}


Надо иметь в виду, что результат имеет погрешность (оперируем случайными величинами).

И опять этот мерзкий С.:)

Ответить

Номер ответа: 4
Автор ответа:
 pinky



ICQ: 218-538-334 

Вопросов: 3
Ответов: 9
 Web-сайт: jimsunweed.com
 Профиль | | #4
Добавлено: 17.10.06 09:51
Можно сделать так (по ходу это то же самое что и предложил Sharp тока непонятно что такое волновой алгоритм=)
 берем первую строку и начиная с первого элемента(если он равен нулю) все встретившиеся нули меняем на еденицы. делаем это до первой встретившейся еденицы, или до конца, если такой нет. если первый элемент равен 1 то ничего не делаем.
 то же самое делаем справа налево.
 потом считаем количество оставшихся нулей.

Ответить

Номер ответа: 5
Автор ответа:
 el-paso



Вопросов: 3
Ответов: 164
 Профиль | | #5 Добавлено: 17.10.06 19:00

Function Solve() As Long
    '
    ' как бы ввод
    Const h = 5
    Const w = 7
    Const s = "0001110,0111010,0100010,0111110,0000000"
    '
    ' разбиваем текст в массив строк
    Dim a() As String: a = Split(s, ",";)
    '
    Dim l As Integer ' счетчик строк
    Dim c As Integer ' счетчик символов в строке
    '
    Dim CountZeroes As Boolean: CountZeroes = False ' флаг: надо ли считать нули
    Dim Zeroes As Integer: Zeroes = 0 ' количество накопленных ноликов
    '
    ' проходим через все строки по очереди...
    For l = 0 To h - 1
        '
        ' сбрасываем флаг (первые ноли в строке никогда не считаются)
        CountZeroes = False
        '
        ' прочесываем все символы в строке - с начала и до последней единицы (не включая ее)
        For c = 1 To InStrRev(a(l), "1";) - 1
            '
            ' если видим переход "10" переключаем флаг (True -> False, False -> True)
            If Mid$(a(l), c, 2) = "10" Then CountZeroes = Not CountZeroes
            ' если символ - нолик, и нолики следует считать, то считаем его
            If Mid$(a(l), c, 1) = "0" And CountZeroes Then Zeroes = Zeroes + 1
            '
        Next
    Next
    '
    ' возвращаем результат
    Solve = Zeroes
    '
End Function

Ответить

Номер ответа: 6
Автор ответа:
 el-paso



Вопросов: 3
Ответов: 164
 Профиль | | #6 Добавлено: 17.10.06 19:06
Хм.. Запостил, и прикинул, что есть баг :))
Если матрица будет вида

1110111
1011101
1000001
1111011
0001110

то посчитает неверно...
Надо подумать...

Ответить

Номер ответа: 7
Автор ответа:
 Sharp


Лидер форума

ICQ: 216865379 

Вопросов: 106
Ответов: 9979
 Web-сайт: sharpc.livejournal.com
 Профиль | | #7
Добавлено: 17.10.06 20:01
vito, это прикол такой? :)
http://algolist.manual.ru/games/wavealg.php

Ответить

Номер ответа: 8
Автор ответа:
 vito



Разработчик Offline Client

Вопросов: 23
Ответов: 879
 Web-сайт: softvito.narod2.ru
 Профиль | | #8
Добавлено: 17.10.06 23:19
 Sharp

Почти.:) Ну считает-же.:)
Волновой алгоритм конечно оптимален. А это для разнообразия.

Ответить

Номер ответа: 9
Автор ответа:
 Sharp


Лидер форума

ICQ: 216865379 

Вопросов: 106
Ответов: 9979
 Web-сайт: sharpc.livejournal.com
 Профиль | | #9
Добавлено: 18.10.06 17:21
Ну в условии же не сказано, что единицы стоят всегда на одних и тех же позициях

Ответить

Номер ответа: 10
Автор ответа:
 vito



Разработчик Offline Client

Вопросов: 23
Ответов: 879
 Web-сайт: softvito.narod2.ru
 Профиль | | #10
Добавлено: 18.10.06 22:43
Sharp
Ну в условии же не сказано, что единицы стоят всегда на одних и тех же позициях


Я немного суть не уловил. Из этого следует, что метод Монте - Карло не применим?

Ответить

Номер ответа: 11
Автор ответа:
 Sharp


Лидер форума

ICQ: 216865379 

Вопросов: 106
Ответов: 9979
 Web-сайт: sharpc.livejournal.com
 Профиль | | #11
Добавлено: 18.10.06 23:06
Точно не в таком виде, как у тебя. Потому что нужно динамически определять, находится ли точка внутри контура - прописать статически условие для этого не получится.

Ответить

Номер ответа: 12
Автор ответа:
 vito



Разработчик Offline Client

Вопросов: 23
Ответов: 879
 Web-сайт: softvito.narod2.ru
 Профиль | | #12
Добавлено: 19.10.06 00:00
Sharp

Потому что нужно динамически определять, находится ли точка внутри контура -

У меня все очень криво:) (в общем и вправду развлекался:), но это, все-же, проверяется динамически.
1.rx=rand()%10;// генерим два случайных числа
ry=rand()%10;

2.if (ry<5 && rx<7)// попали в квалрат?

3. if ((rx==1&& ry==4)||(rx==2&& ry==2)||(rx==2&& ry==3)||(rx==2&& ry==4)||(rx==3&& ry==3)||(rx==5&& ry==2))

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

Статическое условие получилось из-за рассмотрения частного случая (если я правильно понял суть).

И конечно так метод Монте-Карло не реализуется.
Просто частный случай.

Ответить

Номер ответа: 13
Автор ответа:
 el-paso



Вопросов: 3
Ответов: 164
 Профиль | | #13 Добавлено: 19.10.06 00:23
Нде.. Написал.. Только выкладывать не буду, ибо код большой + класс.. И вообще простой VB для таких вещей не слишком подходит - лучше .NET :/

P.S. Волновой алгоритм рулит.

Ответить

Номер ответа: 14
Автор ответа:
 Andrey



Вопросов: 0
Ответов: 1
 Профиль | | #14 Добавлено: 06.11.06 00:58
Есть очень простое решение.
Допустим есть следующая фигура:

1110111 111 111
1011101 ===\ 1 111 1
1000001 ====> 1 1
1111011 ===/ 1111 11
0001110 111

Нули я убрал для наглюдности.
                         X
333333333 333333333 0 X=9
311101113 3111 1113 1 Y=7
310111013 ===\ 31 111 13 2
310000013 ====> Y 31 13 3
311110113 ===/ 31111 113 4
300011103 3 111 3 5
333333333 333333333 6
                     012345678
Делаем рамку чтобы у каждой клетки были
все четыре границы.
Далее идёт сам просчет:

Dim check as Boolean
Dim i, j as Integer

' Тут стоит пояснить зачем нужна переменная check
' Алгоритм проверяет что нет ни одного нуля
' стоящего рядом с рамкой (3) или с другим нулем
' связанным с рамкой (4). Цикл завершится когда
' значение check будет положительно, тоесть когда
' все внешние нули поменяны на 4.

While Not check
    check = True
    For j = 1 To Y - 2 'Проверка строчек 1-5
        For i = 1 To X - 2 'Проверка символов 1-7
            If m[j] = 0 Then 'Работать только с 0
                If m[i-1][j] > 2 Or m[i+1][j] > 2 Or m[j-1] > 2 Or m[j+1] > 2 Then
            'Если один из соседних символов рамка или 0 вне фигуры
                    m[j] = 4 ' 4 это 0 вне фигуры
                    check = False 'Выполнить проверку снова
                End If
            End If
        End For
    End For
Wend


Теперь у нас есть следующая картина:

333333333 333333333 0 X=9
311141113 311141113 1 Y=7
310111013 ===\ 31 111 13 2
310000013 ====> Y 31 13 3
311110113 ===/ 31111 113 4
344411143 344411143 5
333333333 333333333 6

Проходим циклом и ищем количество нулей.
Вот и всё!

Ответить

Страница: 1 |

Поиск по форуму



© Copyright 2002-2011 VBNet.RU | Пишите нам