Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Жук

(Время: 1 сек. Память: 16 Мб Сложность: 30%)

Решением этой задачи является моделирование движения жука. Для этого сначала можно считать в двумерный массив (проще в одномерный массив строк) лабиринт для проверки на столкновение жука со стенами. Для запоминания количества посещений в клетках можно использовать некоторый целочисленный массив A, предварительно обнулив его. На самом деле можно обойтись одним лишь массивом и хранить стенки лабиринта в целочисленном массиве как некоторое отрицательное число, например -1.

Первоначально следует разместить жука в левом верхнем углу, координаты жука можно хранить в некоторых переменных kx и ky, меняя их в момент движения. При каждом шаге после изменения этих координат следует увеличивать значение A[ky][kx]. Помимо координат жука и количества посещений так же нужно запоминать текущее направление движения, т.к. это в определенных случаях влияет на поведение жука. Единственное, что здесь требуется - это аккуратно формализовать алгоритм движения, описанный в условиях задачи.

Возникает вопрос: а можно ли быстро вычислить количество ходов жука, не моделируя этот процесс? Очевидно, что если это и возможно, то очень сложно. По крайней мере решение еще не найдено. Так же не очевидно, что не существует такого лабиринта, который жук не успел бы преодолеть за одну секунду. Более того, наверняка такой лабиринт возможно построить, т.к. на сегодняшний день для лабиринта 30х20 уже существует решение на 16 миллионов ходов, несложно догадаться, что для размеров 100х100 число ходов может существенно возрасти. Тем неменее, тестов таких нет, иначе было бы не ясно: как решать эту задачу. На сайте http://buglab.ru вы можете попытаться побить вышеописанный рекорд. Очевидно, сделать это возможно, только при использовании средств программирования.

Для реализации данной задачи можно использовать код Java Script, который встроен в веб-страницу в формулировке задачи на сайте, наибольший интерес должна вызывать эта функция:

  function MakeMove(){
   var kx2,ky2,down,right,up,left,cur,l,nn=speed;
   if(!go) return;
   do{
    nn*=2
    if((kx==28)&&(ky==6)){
        return
    }else{
      kx2=kx; ky2=ky; n++
      down=M[ky+1][kx]
      right=M[ky][kx+1]
      up=M[ky-1][kx]
      left=M[ky][kx-1]
      if(dir==0) cur=down
      if(dir==1) cur=right
      if(dir==2) cur=up
      if(dir==3) cur=left
      if((cur<=down)&&(cur<=right)&&(cur<=up)&&(cur<=left)){
        if(dir==0) ky2++
        if(dir==1) kx2++
        if(dir==2) ky2--
        if(dir==3) kx2--
      }else
      if((down<=right)&&(down<=up)&&(down<=left)){ky2++;dir=0}else
      if((right<=down)&&(right<=up)&&(right<=left)){kx2++;dir=1}else
      if((up<=right)&&(up<=down)&&(up<=left)){ky2--;dir=2}else
      if((left<=right)&&(left<=down)&&(left<=up)){kx2--;dir=3}
      M[ky][kx]++
      kx=kx2;ky=ky2
    }
   }while(nn<2)
  }

[Обсуждение] [Все попытки] [Задача]


Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru