Олимпиадная задача 2

← →
pumba (2003-01-02 08:15) [0]

Тоже не могу решить(как и первую). Помогите решит хоть какую-нибудь из них!

Задан полигон в виде прямоугольного клеточного поля размером MxN клеток (M и N, определяют размеры полигона вдоль осей OX и ОY соответственно). В углах полигона и, возможно, на сторонах размещены выходы, каждый размером в одну клетку. Левый нижний выход имеет координаты (1,1). Граничные клетки полигона, не являющиеся выходами, образуют упругие стенки. Робот начинает движение с клетки с координатами K, L в одном из восьми направлений (вертикально, горизонтально и по двум диагоналям в обоих направлениях). Робот двигается только по целым клеткам и, натолкнувшись на стенку, продолжает движение с той же скоростью по закону: угол падения равен углу отражения. Необходимо выяснить: останется ли робот на полигоне или покинет его через один из выходов. В последнем случае указать координаты выхода и количество столкновений со стенками. Направления движения Т нумеруються числами от 1 до 8 по часовой стрелке. Направление 1 - вдоль оси Y в направлении увеличения координаты (вверх).
Ввод-вывод
Вы вводите с клавиатуры два натуральных числа M и N (3 <= M <= 1001), (3 <= N <= 1001). Вы вводите с клавиатуры количество неугловых выходов V (0 <= V <= 255), а затем - V пар натуральных чисел - X и Y координаты неуголвых выходов. Далее вводите начальные координаты робота K, L и направление T. Все величины вводятся через пробел.

Вы выводите на экран 0, если робот не может найти выход, а если нашел - три числа через пробел - координаты выхода и количество столкновений.

Примеры

1. Ввод> 14 6 1 10 1 13 5 8
Вывод< 14 6 13
2. Ввод> 11 6 0 4 3 3
Вывод<0

← →
Igorek (2003-01-02 10:43) [1]

А в чем проблема? Можно в лоб так:
Эмулируешь движение робота (это не сложно). Для каждой клетки, по которой он прошел запоминаешь направление движения (учти, что для одной клетки их может быть несколько). По ходу считаешь колл. столкновений со стенками. Если робот попадает в клетку, по которой уже прошел в том же направлении, то прерываешь процес (робот зациклиться). Если робот находит выход - прерываешь и выводишь результат.

← →
pumba (2003-01-02 12:22) [2]

<h2>To Igorek:</h2>

>По ходу считаешь колл. столкновений со стенками. Если робот >попадает в клетку, по которой уже прошел в том же направлении, >то прерываешь процес (робот зациклиться). Если робот находит >выход - прерываешь и выводишь результат.

Это я с легкостью могу сделать, а как сделать следующее:
>Эмулируешь движение робота (это не сложно). Для каждой клетки, >по которой он прошел запоминаешь направление движения

???????????

Я человек начинающий, поэтому еще мне много не понятно.

← →
Yegor Derevenets (2003-01-02 14:23) [3]

Для каждой клетки стоит завести массивчик [1..8] of Boolean (или байтовую переменную и помучаться с битовой арихметикой). Сначала всё там фальш или 0. Каждый момент движения мы смотрим, в каком направлении движется робот. Смотрим для текущей клетки, двигался ли он в этом направлении уже в этой клетки. Если двигался, то ... :-) Иначе - помечаем в клеточном массиве соответствующий направлению (можно направления задать константами от 1 до 8) элемент как тру. Если мы вдруг оказались в клетке, которая выход, то ... .
Отражение от стенок можно и case-ом сделать... Если мы напоролись на стенку (то есть по направлению движения двигаться уже нельзя, то меняем напрваление на противоположное). И не забывать инкрементировать число отражений...
В принципе, написать не сложно. Сам бы написал, только как-то вломно после Нового Года. :-)
Вообще, судя по ограниченями, стоит использовать вместо массива для каждой клетки байтовую переменную. Тогда константы для направлений будут 1, 2, 4, 8, 16, 32, 64, 128. Добавление направления в список для клетки: A [i, j].Vectors:=A [i, j].Vectors or VectorConst. Проверка, было ли оно уже пройдено - (A [i, j].Vectors and VectorConst<>0).
Странно. Уже половину написал. :-)
Вобщем, массив будет что-то вроде A: array [1..MaxN, 1..MaxM] of record Vector, CellType: Byte; end;
Можно даже packed ко всему приписать. :-)
Удачи. :-)
Если надоест писать клон аськи, то, возможно, сегодня напишу.

← →
Sha (2003-01-02 15:15) [4]

2 Yegor Derevenets (02.01.03 14:23)

Оставь автору что-нибудь, а то ему будет неинтересно.

← →
Yegor Derevenets (2003-01-02 15:30) [5]

2 Sha
Эта задача IMHO будет попроще первой, так что пусть люди сами за себя решают. Это было последнее моё сообщение. Кому что надо - мой e-mail или ICQ: 138994073. I`m online for 2 next hours. :-)

← →
Choor (2003-01-03 20:17) [6]

Решение отослал.

← →
Hiqwer (2003-01-04 18:39) [7]

>Yegor Derevenets and All
Предложенный алгоритм имеет серьезную абщипку... и решением не является.

Предположим, что через одну клетку робот проходит трижды за цикл.
1 и 3 раз в одном направлении (как раз "зацикливание"), а во 2 в другом. При проверке на 3 проходе направление будет сверено с направлением второго прохода и зацикливание не обнаружится.

Верное решение иное.

← →
BofA (2003-01-04 20:32) [8]

2 Hiqwer
Внимательнее читай, твой пример будет корректно обработан!

Олимпиадная задача 2 Найти похожие ветки