С Новым годом! Форум программистов, компьютерный форум, киберфорум
PascalABC.NET
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.90/21: Рейтинг темы: голосов - 21, средняя оценка - 4.90
3 / 3 / 0
Регистрация: 05.06.2019
Сообщений: 82

Робинзон и крокодилы

14.01.2020, 22:27. Показов 4597. Ответов 12
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Робинзон живет на острове, который представляет собой прямоугольник размером n × m клеток.

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

В каждой клетке острова находится не более одного крокодила. Напуганный орехом крокодил быстро бежит строго по прямой, пока не окажется в воде. Для каждого крокодила известно направление, в котором он побежит, если его напугать. Направления, в которых будут убегать крокодилы, параллельны сторонам острова.

Если на пути напуганного крокодила окажется другой крокодил, то, столкнувшись, они разозлятся, и нападут на Робинзона. Поэтому надо тщательно выбирать очередного крокодила, чтобы на его пути были только пустые клетки.

Робинзон не кидает очередной орех, пока предыдущий крокодил не окажется в воде.

Требуется написать программу, определяющую максимальное количество крокодилов, которых можно прогнать, не разозлив их.

Формат ввода
В первой строке входного файла записаны числа n и m "— размеры острова с севера на юг и с запада на восток. Последующие n строк по m символов в каждой описывают текущее расположение крокодилов на острове. Если клетка свободна, то она обозначается точкой «.», а если там находится крокодил, то в ней указано направление, в котором побежит этот крокодил. Направления обозначаются буквами: «N» "— север, «S» "— юг, «E» "— восток, «W» "— запад.

Формат вывода
Выходной файл должен содержать одно число "— максимальное количество крокодилов, которых можно прогнать, не разозлив.

Пример 1
Ввод
1 5
WN.SE
Вывод
4

Пример 2
Ввод
1 3
E.W
Вывод
0


Пример 3
Ввод
3 4
.N.W
WWSS
EWEW
Вывод
4


Помогите пожалуйста решить задачу, вот мой код:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
var
  a: array [,] of char;
  n, m, x, y, count: integer;
  Yes, changed: boolean;
 
procedure scan;
var x_1, y_1: integer;
begin
  if not changed Then
    exit
  else
    begin
    changed := False;
    for var x := 0 to n - 1 do
      for var y := 0 to m - 1 do
      begin
        Yes := True;
        if a[x, y] = 'N' Then
        begin
          for x_1 := x - 1 downto 0 do
            if a[x_1, y] <> '.' Then
            begin
              Yes := False;
              break; 
            end;     
        end
        else
        if a[x, y] = 'S' Then
        begin
          for x_1 := x + 1 to n - 1 do
            if a[x_1, y] <> '.' Then
            begin
              Yes := False;
              break; 
            end;    
        end
        else
        if a[x, y] = 'W' Then
        begin
          for y_1 := y - 1 downto 0 do
            if a[x, y_1] <> '.' Then
            begin
              Yes := False;
              break; 
            end;    
        end
        else
          if a[x, y] = 'E' Then
        begin
          for y_1 := y + 1 to m - 1 do
            if a[x, y_1] <> '.' Then
            begin
              Yes := False;
              break; 
            end;    
        end
        else
          continue;
        
        
        if Yes Then
        begin          
          changed := True;
          a[x, y] := '.';
          inc(count);
        end;
      end;
    scan();
  end;
end;
 
 
begin
  readln(n, m);  
  SetLength(a, n, m);  
  for x := 0 to n - 1 do
  begin
    for y := 0 to m - 1 do      
      read(a[x, y]);
    readln();
  end;
  //N, S, W, E
  changed := True;
  scan();
  writeln(count);
end.
Насколько я понял, дело в куче циклов + рекурсия, подскажите, пожалуйста, как упростить?
Миниатюры
Робинзон и крокодилы  
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
14.01.2020, 22:27
Ответы с готовыми решениями:

Робинзон и крокодилы
Люди хелп, спасайте. Надо выручить человека. Может кто уже решал эти задачи, скиньте приз код 1)Задача Y. Робинзон и крокодилы Имя...

Красавицы и крокодилы
Здравствуйте!!! Вот возник не давно такой вопрос....и мучает постоянно..... почему все девочки когда маленькие......все красавицы, а...

Робинзон и Пятница на необитаемом острове
Ребят помогите пожалуйста решить, буду очень благодарен. 3. Могут ли следующие точки лежать на одной кривой производственных...

12
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
15.01.2020, 00:42
двусвязный список наверное тут надо использовать
1
 Аватар для JuriiMW
5095 / 2661 / 2355
Регистрация: 10.12.2014
Сообщений: 10,059
15.01.2020, 06:27
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
begin
  var(rows,cols):=ReadLnInteger2;
  var a:array [,] of Integer;
  Setlength(a,rows,cols);
  for var row:=0 to rows-1 do
    begin
      var s:=ReadLnString;
      for var col:=0 to cols-1 do
        case s[col+1] of
          '.' : a[row,col]:=0;
          'N' : a[row,col]:=1;
          'S' : a[row,col]:=2;
          'E' : a[row,col]:=3;
          'W' : a[row,col]:=4;
        end;
    end;
    
  var count:=0;
  repeat
    var pred:=count;
    
    for var row:=0 to rows-1 do
      for var col:=0 to cols-1 do
        if a[row,col]>0 then
          begin
            var s:=0;
            case a[row,col] of
              1 : for var r:=0 to row-1 do s+=a[r,col]; // N : row-1
              2 : for var r:=row+1 to rows-1 do s+=a[r,col]; // S : row+1
              3 : for var c:=col+1 to cols-1 do s+=a[row,c]; // E : col+1
              4 : for var c:=0 to col-1 do s+=a[row,c]; // W : col-1
            end;
            if s=0 then begin a[row,col]:=0; count+=1; end;
          end;
    
    if pred = count then Break;
  until False;
  
  count.Println;
end.
Просто проверяем всех крокодилов есть ли по его направлению движения другие
(сумма = 0 — нет, иначе — есть)
и, в случае отсутствия, убираем его из массива.
1
3 / 3 / 0
Регистрация: 05.06.2019
Сообщений: 82
15.01.2020, 09:40  [ТС]
К сожалению ничего не изменилось...
0
 Аватар для JuriiMW
5095 / 2661 / 2355
Регистрация: 10.12.2014
Сообщений: 10,059
15.01.2020, 09:43
А что должно и где измениться?
0
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
15.01.2020, 09:44
sadfasfsad, А что должно измениться?
Программа просто переписана на case и убрана рекурсия.
Сложность алгоритма осталась прежней.
0
3 / 3 / 0
Регистрация: 05.06.2019
Сообщений: 82
15.01.2020, 09:46  [ТС]
Как можно ускорить выполнение программы? Ошибка именно в этом.
0
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
15.01.2020, 10:25
1) Для каждого крокодила запоминаете его соседей.
WN.SE

W ..N.
N W.S.
S N.E.
E S...

2) Проверяем крокодилов:
W не можен убежать так как в этом направлении есть крокодил
N можут убежать:
-удаляем его у соседей и его самого удаляем.
W ....
S ..E.
E S...
проверяем его соседей W и S удаляем если может убежать также или пропускаем
и т.д

пока такая идея
0
3 / 3 / 0
Регистрация: 05.06.2019
Сообщений: 82
15.01.2020, 10:41  [ТС]
Насколько я понял в первом примере, они сразу все убегут, т.к. мы начинаем кидать с лево на право, а они направлены в разные стороны. N и S убегут сразу, а E убежит, т.к. W уже убежал
0
 Аватар для JuriiMW
5095 / 2661 / 2355
Регистрация: 10.12.2014
Сообщений: 10,059
15.01.2020, 11:09
sadfasfsad, сайт тестирования давайте…
0
3 / 3 / 0
Регистрация: 05.06.2019
Сообщений: 82
15.01.2020, 11:10  [ТС]
https://contest.yandex.ru/roi/contest/999/enter
0
 Аватар для mr-Crocodile
3053 / 1672 / 657
Регистрация: 19.03.2019
Сообщений: 5,381
15.01.2020, 11:40
Цитата Сообщение от eaa Посмотреть сообщение
W не можен убежать так как в этом направлении есть крокодил
предположу, что перепутались стороны света.
в данной задаче так:
1
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
15.01.2020, 11:42
mr-Crocodile, да. перепутал, спсб
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
15.01.2020, 11:42
Помогаю со студенческими работами здесь

Олимпиадные Задачи (Робинзон живет на острове)
Здравствуйте. Помогите ,пожалуйста. Решаю одну задачу по программированию на питоне. Вот условие: Ограничение по времени: 2 секунды ...

как померить ток или крокодилы для импортного тестера
подскажите пожалуйста как померить колекторный ток Тр пока был советский тестер, пользовался кондовыми проводами с крокодилами ...

Робинзон, будучи на необитаемом острове, считал прожитые дни
:wall: Помогите :gcray: Робинзон, будучи на необитаемом острове, считал прожитые дни. Когда корабль забрал Робинзона с необитаемого...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Новые блоги и статьи
Новый CodeBlocs. Версия 25.03
palva 04.01.2026
Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .
Модель микоризы: классовый агентный подход
anaschu 02.01.2026
Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .
Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути
Programma_Boinc 01.01.2026
Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути Сочетание глобально распределённой вычислительной мощности и инновационных. . .
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Programma_Boinc 28.12.2025
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / **********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / **********/ gallery/ bKBkQFf Пост отсюда. . .
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru