 количество вариантов расположения кораблей на игровом поле, морской бой |
| LLL |
 9.11.2009 12:23
Сообщение
#1
|
|
Группа: Пользователи Сообщений: 1 Пол: Женский Репутация:  0   |
Помогите, пожалуйста, решить задачу: (задача олимпиадная 10 класс)
на поле размером N*M (1<=N<=10,1<=M<=15) расставляются 4 корабля: однопалубный, 2-палубный,3-палубный и 4-палубный.Корабли могут располагатся вертикально и горизонтально, не соприкасаясь друг с другом углами и границами. Требуется определить количество вариантов расположения кораблей на игровом поле. |
   |
 
|
  |
Ответов
| andriano |
9.11.2009 13:25
Сообщение
#2
|
|
Гуру  Группа: Пользователи Сообщений: 1 168 Пол: Мужской Реальное имя: Сергей Андрианов Репутация: 28 |
На самом деле, раз корабли не могут соприкасаться, при переборе просто нужно вместе с установкой корабля, делать занятыми клетки вокруг него.
Ну и сам перебор, естественно вести в диапазоне (M-1, N-2) клеток. Для увеличения скорости перебора я бы каждому полю ставил в соответствие 1 бит, тогда, учитывая, что максимальные 15 клеток укладываются в 16-разрядный регистр, просмотр всего поля состоял бы всего из 10 операций сравнения. Можно, использую 32-разрядные регистры, сократить количество операций до 5 или MMX - до трех. |
|
|
|
Сообщений в этой теме
LLL количество вариантов расположения кораблей на игровом поле 9.11.2009 12:23
RathaR Ну для начала, ты ведь сама говоришь о задаче, сле... 9.11.2009 12:41 RathaR А почему бы не пойти "в лоб"...
Допустим... 9.11.2009 17:24 andriano Ну, вообще-то этой функции еще надо передавать тек... 9.11.2009 20:18
Lapp Это либо 4 32-разрядных числа, либо 2 регистра ММХ... 10.11.2009 5:41 andriano
andriano неисправим.. Хлебом не корми - дай уско... 10.11.2009 9:44 Lapp Спасибо))
Кстати, я уверен, что отлаживал задачу т... 10.11.2009 10:00 andriano
Спасибо))
Я начал с 4x4 Просто споткнулся об это ... 10.11.2009 10:29 Lapp > только дочитав:понял, то такое возможно.
)) н... 10.11.2009 10:53 andriano Я их рассматривал... скажем так: наполовину. Цик... 10.11.2009 11:20 Lapp "Минус хвост", если я не ошибаюсь, означ... 10.11.2009 11:33 andriano
Первое.В обще-то, очевидно. Просто на всякий случ... 10.11.2009 11:57 Lapp Может, как раз выше описанный?
Нет, совсем другой ... 10.11.2009 12:40 Lapp Нет, совсем другой :no1:
...
Да, пожалуй, можно ... 10.11.2009 14:45 RathaR
Отчего же?
Помойму если в задаче сказано найти ... 10.11.2009 11:34 RathaR А может всётаки перенесёте тему в раздел задач, к ... 10.11.2009 11:14 Lapp Первый способ (через игровое поле)
const
n= 10;
... 10.11.2009 14:43 Lapp Подумал, что уже можно открыть в любом случае. Жа... 18.11.2009 15:16 |
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
Текстовая версия | 10.07.2025 10:07 |