Олимпиадные Задачи (Робинзон живет на острове)

@spyteamalex · Регистрация: 25.01.2018

Студворк — интернет-сервис помощи студентам

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

Ограничение по времени: 2 секунды
Ограничение по памяти: 512 мегабайт

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

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

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

Пример:
Входные данные:
3 4
.N.W
WWSS
EWEW
Выходные Данные:
4

Вот написанный мною код на питоне и С++(Пробовал, вдруг будет работать быстрее):

Python
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
def is_free(y,x,t,island):
    if t == 'N':
        if y-1 < 0:
            return True
        if island[y-1][x] == '.':
            return is_free(y-1,x,t,island)
        else:
            return False
             
    if t == 'S':
        if y+1 >= len(island):
            return True
        if island[y+1][x] == '.':
            return is_free(y+1,x,t,island)
        else:
            return False
    if t == 'E':
        if x+1 >= len(island[y]):
            return True
        if island[y][x+1] == '.':
            return is_free(y,x+1,t,island)
        else:
            return False
    if t == 'W':
        if x-1 < 0:
            return True
        if island[y][x-1] == '.':
            return is_free(y,x-1,t,island)
        else:
            return False
    if t == '.':
        return False
 
def is_ready(island):
    for i in range(0,len(island)):
        for j in range(0,len(island[i])):
            if island[i][j] != '.':
                if is_free(i,j,island[i][j],island):
                    return False
    return True
     
     
 
size = input().split(' ')
size[0]=int(size[0])
size[1]=int(size[1])
count=0
island = []
for i in range(0,size[0]):
    island.append(list(input()))
while not is_ready(island):
    for i in range(0,size[0]):
        for j in range(0,size[1]):
            if island[i][j] != '.':
                if is_free(i,j,island[i][j],island):
                    count+=1
                    island[i][j]='.'
print(count)

C++
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
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
bool is_free(int y, int x, char t, int island[500][500]);
bool is_ready();
int size[2];
int i;
int j;
int island[500][500];
 
int main(){
    cin >> size[0] >> size[1];
 
    int count = 0;
    string line;
    for (i = 0; i < size[0]; i++){
        cin >> line;
        for (j = 0; j < size[1]; j++){
            island[i][j] = line[j];
        }
    }
        while (!is_ready()) {
            for (i = 0; i < size[0]; i++)
                for (j = 0; j < size[1]; j++)
                    if (island[i][j] != '.')
                        if (is_free(i, j, island[i][j], island))
                        {
                            count += 1;
                            island[i][j] = '.';
                        }
        }
    
    cout << count;
    cin >> count;
    return 0;
}
 
bool is_free(int y, int x, char t, int island[500][500]){
    switch (t){
    case 'N':
        while (y - 1 >= 0){
            y--;
            if (island[y][x] != '.'){
                return false;
            }
        }
        return true;
        break;
    case 'S':
        while (y + 1 < size[0]){
            y++;
            if (island[y][x] != '.'){
                return false;
            }
        }
        return true;
        break;
    case 'E':
            while (x + 1 < size[1]){
                x++;
                if (island[y][x] != '.'){
                    return false;
                }
            }
            return true;
            break;
        case 'W':
            while (x - 1 >= 0){
                x--;
                if (island[y][x] != '.'){
                    return false;
                }
            }
            return true;
            break;
        case '.':
            return false;
    }
}
 
bool is_ready() {
    for (i = 0; i < size[0]; i++){
        for (j = 0; j < size[1]; j++){
            if (island[i][j] != '.'){
                if (is_free(i, j, island[i][j], island)){
                    return false;
                }
            }
        }
    }
    return true;
}

При входных данных 1 ≤ n, m ≤ 30 все работает хорошо, но при 1 ≤ n, m ≤ 500 уже не укладывается в 2 секунды. Помогите ,пожалуйста, ускорить программу.

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

@dondublon · 26.01.2018, 15:03

Рекурсия - штука ресурсоёмкая и в данном случае совершенно ненужная.
Кроме того, вызов is_free в is_ready вообще непонятен, похоже, вы там для каждой клетки кучу проходов делаете.
Воспользуйтесь функцией all.
Тут хорошо можно сделать с numpy и его двумерными массивами, но, если его использовать нельзя - напишите обёртку для прохода клеток острова по вертикали.

@Shamil1 · 26.01.2018, 15:57

Пусть K - количество крокодилов (K <= M*N).

1. Для каждого крокодила O(K) вычисляем количество мешающих крокодилов O(N+M) и помещаем крокодила в очередь с приоритетом O(logK).
2. Находим крокодила, которому никто не мешает O(1). Удаляем его с поля O(logK). Для каждого крокодила, которому он мешал O(N+M), уменьшаем количество мешающих крокодилов O(logK).
3. Повторяем п.2 пока есть крокодилы, которым никто не мешает O(K).
Итого O( max(M*N, K*(M+N)*logK) )

Можно ещё количество мешающих крокодилов считать за O(1) и хранить крокодилов, которым мешаешь, в списке. Тогда ещё быстрее. Но при максимально возможном количестве крокодилов, это не даст ускорения.

@Shamil1 · 02.02.2018, 00:02

Примерно так:

Python
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
class BinaryHeap:
    def __init__(self):
        self.data = []
 
    def add(self, item):
        item.index = len(self.data)
        self.data.append(item)
        self.move_up(item.index)
        return item
 
    def remove_max(self):
        if not self.data:
            return None
        res = self.data[0]
        item = self.data.pop()
        if self.data:
            item.index = 0
            self.data[0] = item
            self.move_down(0)
        return res
 
    def pick_max(self):
        if not self.data:
            return None
        return self.data[0]
 
    def move_up(self, i):
        while i > 0:
            p = (i - 1) // 2         #parent
            if self.data[p].count < self.data[i].count:
                break
            self.data[p], self.data[i] = self.data[i], self.data[p]
            self.data[p].index, self.data[i].index = p, i
            i = p
 
    def move_down(self, i):
        while True:
            m = i
            l = (i + 1) * 2 - 1      #left
            if l >= len(self.data):
                break
            if self.data[l].count < self.data[m].count:
                m = l
            r = (i + 1) * 2          #right
            if r < len(self.data) and self.data[r].count < self.data[m].count:
                m = r
            if m == i:
                break
            self.data[m], self.data[i] = self.data[i], self.data[m]
            self.data[m].index, self.data[i].index = m, i
            i = m
 
            
class Crocodile:
    def __init__(self, direction, count, row, col, index):
        self.direction = direction
        self.count = count
        self.row = row
        self.col = col
        self.index = index
 
    def print(self):
        print(f'Crocodile: direction={self.direction}, count={self.count}, row={self.row}, col={self.col}, index={self.index}')
        
 
def solve(a):
    directions = ['N', 'W', 'S', 'E']
    oposites = {'N':'S', 'W':'E', 'S':'N', 'E':'W'}
    n, m = len(a), len(a[0])
 
    def get_crocodiles(row, col, direction):
        if direction == 'N':
            return ((r,col) for r in range(0, row) if a[r][col] != '.')
        if direction == 'S':
            return ((r,col) for r in range(row+1, n) if a[r][col] != '.')
        if direction == 'W':
            return ((row,c) for c in range(0, col) if a[row][c] != '.')
        if direction == 'E':
            return ((row,c) for c in range(col+1, m) if a[row][c] != '.')
 
    heap = BinaryHeap()
    for row in range(n):
        for col in range(m):
            if a[row][col] != '.':
                count = sum(1 for _ in get_crocodiles(row, col, a[row][col]))
                croc = Crocodile(a[row][col], count, row, col, 0)
                heap.add(croc)
                a[row][col] = croc
    total = len(heap.data)
 
    while (len(heap.data) > 0):
        if heap.pick_max().count > 0:
            break;
        croc = heap.remove_max()
        for cr in (a[r][c] for d in directions for r,c in get_crocodiles(croc.row, croc.col, d)
                   if d != croc.direction and a[r][c].direction == oposites[d]):
            cr.count -= 1
            heap.move_up(cr.index)
        a[croc.row][croc.col] = '.'
 
    return total - len(heap.data)
 
text ='''3 4
.N.W
WWSS
EWEW'''
res = solve([list(s) for s in text.splitlines()[1:]])
print(res)

Но я не тестировал - убедился только, что работает на данном лабиринте. Если найдётся лабиринт, на котором не работает, я могу посмотреть, в чём дело.

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. 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. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

@dondublon 4652 / 2072 / 366 Регистрация: 17.03.2012 Сообщений: 10,181 Записей в блоге: 6
	26.01.2018, 15:03
	Рекурсия - штука ресурсоёмкая и в данном случае совершенно ненужная. Кроме того, вызов is_free в is_ready вообще непонятен, похоже, вы там для каждой клетки кучу проходов делаете. Воспользуйтесь функцией all. Тут хорошо можно сделать с numpy и его двумерными массивами, но, если его использовать нельзя - напишите обёртку для прохода клеток острова по вертикали. 0

@Shamil1 Модератор 3133 / 2280 / 469 Регистрация: 26.03.2015 Сообщений: 8,874
	26.01.2018, 15:57
	Сообщение было отмечено spyteamalex как решение Решение Пусть K - количество крокодилов (K <= MN). 1. Для каждого крокодила O(K) вычисляем количество мешающих крокодилов O(N+M) и помещаем крокодила в очередь с приоритетом O(logK). 2. Находим крокодила, которому никто не мешает O(1). Удаляем его с поля O(logK). Для каждого крокодила, которому он мешал O(N+M), уменьшаем количество мешающих крокодилов O(logK). 3. Повторяем п.2 пока есть крокодилы, которым никто не мешает O(K). Итого O( max(MN, K(M+N)logK) ) Можно ещё количество мешающих крокодилов считать за O(1) и хранить крокодилов, которым мешаешь, в списке. Тогда ещё быстрее. Но при максимально возможном количестве крокодилов, это не даст ускорения. 1

Олимпиадные Задачи (Робинзон живет на острове)

Решение