Остров

@MaxGlock · Регистрация: 21.03.2020

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

Доброе время суток, решаю олимпиадную задачу:
На клетчатой бумаге нарисована карта острова (клетки острова закрашены). При этом остров является клетчато-выпуклой фигурой, то есть каждая горизонтальная или вертикальная линия на карте либо не пересекает остров, либо пересекает его по отрезку (линия пересечения не содержит разрывов). Также остров является связной фигурой, то есть любые две клетки острова соединены путём, каждые две соседние клетки которого имеют общую сторону.
Клетка считается соседней с островом, если она не принадлежит острову, но имеет общую сторону или угол с одной из клеток острова.
Самолёт должен облететь вокруг острова по соседним с ним клеткам, не вторгаясь на территорию острова. Программа должна составить маршрут полёта самолёта. Самолёт начинает облёт острова в одной из соседних клеток с островом и должен побывать во всех клетках, соседних с островом, ровно один раз. При этом самолёт может перемещаться из одной клетки в другую клетку, только если эти клетки имеют общую сторону.

Формат входного файла

Программа получает на вход два числа N и M, записанные в отдельных строках, — количество строк и столбцов карты острова (3≤N≤100,3≤M≤100). Далее записана карта острова — N строк, каждая содержащая M символов. Каждый символ карты может быть либо символом «.», что означает клетку, не принадлежащую острову, либо символом «#», что означает клетку острова. При этом остров не касается края карты.

Введём на карте систему координат. Первая координата является номером строки, строки нумеруются сверху вниз числами от 1 до N. Вторая координата — номер столбца, столбцы нумеруются слева направо числами от 1 до M.

Формат выходного файла

Программа должна вывести координаты клеток карты в порядке их облёта самолётом. Каждая строка вывода должна содержать два числа x и y — координаты самолёта, записанные через пробел (1≤x≤N,1≤y≤M). Самолёт должен побывать в каждой соседней с островом клетке ровно один раз. Каждые две клетки, идущие подряд в выводе, должны иметь общую сторону. Можно вывести любой возможный маршрут облёта острова.
Примеры
Ввод
6
7
.......
.......
.......
.###...
.###...
.......
вывод:
3 1
3 2
3 3
3 4
3 5
4 5
5 5
6 5
6 4
6 3
6 2
6 1
5 1
4 1

код имеется, но он громоздок, работает только для прямоугольных островов, и то не для всех
вот он:

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
N=int(input())
M=int(input())
A=[list(input()) for i in range(N)]
z=[]
w=[]
d=[]
f=[]
x=0
a=0
#->
for i in range(1, N):
    for j in range(1, M):
        if A[i][j]=='#' and A[i-1][j-1]!='#' and A[i-1][j+1]!='#' and A[i-1][j]!='#':
            A[i-1][j-1]='*'
            A[i-1][j+1]='*'
            A[i-1][j]='*'
for i in range(N):
    for j in range(M):
        if A[i][j]=='*':
            z.append([i, j])
        if A[i][j]=='.' and A[i][j-1]=='*' and j!=M-1:
            x=j-1
#|            
#\/
for i in range(1, N):
    if A[i][x-1]=='#' and A[i-1][x]!='#' and A[i+1][x]!='#' and A[i][x]!='#':
        A[i-1][x]='*'
        A[i+1][x]='*'
        A[i][x]='*'
        
for i in range(N):
    if A[i][x]=='*' and [i, x] not in z:
        z.append([i, x])
        a=i
x=a
 
#<-
for j in range(M):
    if A[x-1][j]=='#' and A[x][j+1]!='#' and A[x][j-1]!='#' and A[x][j]!='#':
        A[x][j+1]='*'
        A[x][j-1]='*'
        A[x][j]='*'
for j in range(M):
    if A[x][j]=='*' and [x, j] not in z:
        w.append([x, j])
z.extend(w[::-1])
w=[]
for i in range(len(z)):
    for j in range(2):
        x=z[i][j]
 
#/\
#|
for i in range(N):
    if A[i][x+1]=='#' and A[i-1][x]!='#' and A[i+1][x]!='#' and A[i][x]!='#':
        A[i-1][x]='*'
        A[i+1][x]='*'
        A[i][x]='*'
for i in range(N):
    if A[i][x]=='*' and [i, x] not in z:
        w.append([i, x])
z.extend(w[::-1])
for i in range(len(z)):
    for j in range(2):
        z[i][j]+=1
for i in z:
        print(*i)

я в отчаянье, не знаю, как это улучшить

@codcw · 07.04.2020, 20:13

мне кажется можно попробовать так:
глянуть какие клетки есть в радиусе 1 клетки от текущей:
если снизу есть клетки - двигаемся вправо,
если слева есть клетки - двигаемся вниз,
если сверху есть клетки - двигаемся влево,
если справа есть клетки - двигаемся вверх
конечно, это очень обобщенные условия, но думаю суть понятная

@MaxGlock · 08.04.2020, 09:21 **[ТС]**

codcw, спасибо за совет

@codcw · 08.04.2020, 11:06

MaxGlock, задача мне показалась очень интересная, так что захотелось выполнить её самому - вот решение, если интересно. Требует доработок, но мне уже лень

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
a = [['.','.','.','.','.','.','.'],
     ['.','.','.','.','.','.','.'],
     ['.','.','#','#','#','.','.'],
     ['.','#','#','#','#','#','.'],
     ['.','#','#','#','#','#','.'],
     ['.','.','#','#','#','.','.'],
     ['.','.','.','.','.','.','.']]
start = [0,0]
 
for i in range(len(a)):
    try:
        start = [i, a[i].index("#")-1]
        break
    except ValueError:
        pass
 
x = [start[0]-1,start[1]]
 
m = ((-1,-1),
     (-1,0),
     (-1,1),
     (0,1),
     (1,1),
     (1,0),
     (1,-1),
     (0,-1))
 
near = {'topleft':[],
        'top':[],
        'topright':[],
        'right':[],
        'bottomright':[],
        'bottom':[],
        'bottomleft':[],
        'left':[]}
 
result = ''
 
while x != start:
    cnt = 0
    for i in near.keys():
        near[i] = [m[cnt][0] + x[0], m[cnt][1] + x[1]]
        if (near[i][0] < 0) or (near[i][1] < 0) or (near[i][1] > len(a)-1) or (near[i][0] > len(a)-1):
            near[i] = [start[0],start[1]]
        cnt+=1
    
    print(near)
    if a[near['bottom'][0]][near['bottom'][1]] == '#' and a[near['right'][0]][near['right'][1]] == '#':
        x[0] -= 1
    elif a[near['top'][0]][near['top'][1]] == '#' and a[near['right'][0]][near['right'][1]] == '#':
        x[1] -= 1
    elif a[near['top'][0]][near['top'][1]] == '#' and a[near['left'][0]][near['left'][1]] == '#':
        x[0] += 1
    elif a[near['bottom'][0]][near['bottom'][1]] == '#' and a[near['left'][0]][near['left'][1]] == '#':
        x[1] += 1
    elif a[near['bottom'][0]][near['bottom'][1]] == '#':
        x[1] += 1
    elif a[near['left'][0]][near['left'][1]] == '#':
        x[0] += 1
    elif a[near['top'][0]][near['top'][1]] == '#':
        x[1] -= 1
    elif a[near['right'][0]][near['right'][1]] == '#':
        x[0] -= 1
    elif a[near['topright'][0]][near['topright'][1]] == '#':
        x[0] -= 1
    elif a[near['topleft'][0]][near['topleft'][1]] == '#':
        x[1] -= 1
    elif a[near['bottomleft'][0]][near['bottomleft'][1]] == '#':
        x[0] += 1
    elif a[near['bottomright'][0]][near['bottomright'][1]] == '#':
        x[1] += 1
        
    print(x)
    result += str(x)
    
print(result)

@MaxGlock · 08.04.2020, 12:44 **[ТС]**

codcw, XD, ну ладно, сам дороботаю)))

@u235 · 08.04.2020, 19:19

codcw, я, наверное, бы решил эту задачу как-то так:
1. перевел бы карту в бинарную матрицу. 0-, 1- #
2. Свертка с матрицей весов 3х3 (м.б. 2х2 тоже пойдет), типа [[1, 2,4],[8,16,32],[64,128,256]] В результате получившиеся значение будет кодировать локальное окружение точки.
3. Таблица подстановки, каждому полученному в п.2 значению ставится в соответствие 0 или 1. В итоге получаем контур.
4. Находим центр масс контура и переводим координаты контура в полярные из центра масс.
5. Сортируем список декартовых координат точек, используя ключ - полярный угол.

2 и 3 можно заменить эрозией и xor c исходной картой для выделения контура. (можно задействовать PIL)., м.б. это все также можно заменить на свертку с лапласианом.

@codcw · 09.04.2020, 05:07

u235,

Сообщение от u235

1. перевел бы карту в бинарную матрицу. 0-, 1- #

круто, первый пункт понял

остальные можно даже не объяснять, не моего это ума вещи, не дойдет

@u235 · 09.04.2020, 14:50

codcw, как то так, если нигде размерности не перепутал...

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
from PIL import Image, ImageFilter, ImageChops
import math
a = [['.','.','.','.','.','.','.'],
     ['.','.','.','.','.','.','.'],
     ['.','.','#','#','#','.','.'],
     ['.','#','#','#','#','#','.'],
     ['.','#','#','#','#','#','.'],
     ['.','.','#','#','#','.','.'],
     ['.','.','.','.','.','.','.']]
sz=(len(a),len(a[0]))
flat_list = [j=='.' for i in a for j in i]
image=Image.new('1', sz)
image.putdata(flat_list)
contour=ImageChops.difference(image, image.filter(ImageFilter.MinFilter(3)))
# contour - картинка содержащая контур острова
contour_list=list(contour.getdata())
points=[divmod(i,sz[1]) for i in range(len(contour_list)) if contour_list[i]]
# points -список точек контура
points_x,points_y=zip(*points)
avg=lambda x: sum(x)/len(x)
mean_x=avg(points_x)
mean_y=avg(points_y)
phase=[(math.atan2(points_y[i]-mean_y, points_x[i]-mean_x),i) \
       for i in range(len(points))] 
phase.sort()
for i in range(len(points)):
    print(*points[phase[i][1]])

Добавлено через 14 минут
p.s. координаты начинаются с 0. при необходимости добавить единицу.

Добавлено через 4 часа 47 минут
была ошибка с размерностями, поправил:

Кликните здесь для просмотра всего текста

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
from PIL import Image, ImageFilter, ImageChops
import math
 
a = [['.','.','.','.','.','.','.'],
      ['.','.','.','.','.','.','.'],
      ['.','.','.','.','.','.','.'],
      ['.','#','#','#','.','.','.'],
      ['.','#','#','#','.','.','.'],
      ['.','.','.','.','.','.','.']]      
      
sz=(len(a[0]), len(a))
flat_list = [j=='.' for i in a for j in i]
image=Image.new('1', sz)
image.putdata(flat_list)
contour=ImageChops.difference(image, image.filter(ImageFilter.MinFilter(3)))
# contour - картинка содержащая котур острова
contour_list=list(contour.getdata())
points=[divmod(i,sz[0]) for i in range(len(contour_list)) if contour_list[i]]
# points -список точек контура
points_x,points_y=zip(*points)
avg=lambda x: sum(x)/len(x)
mean_x=avg(points_x)
mean_y=avg(points_y)
phase=[(math.atan2(points_y[i]-mean_y, points_x[i]-mean_x),i) \
       for i in range(len(points))] 
phase.sort()
for i in range(len(points)):
    print(*points[phase[i][1]])

@TarKovNet · 09.12.2021, 16:08

Кто-то может перевести это в С++. Заранее спасибо!

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@codcw 815 / 527 / 214 Регистрация: 22.12.2017 Сообщений: 1,495
	07.04.2020, 20:13
	мне кажется можно попробовать так: глянуть какие клетки есть в радиусе 1 клетки от текущей: если снизу есть клетки - двигаемся вправо, если слева есть клетки - двигаемся вниз, если сверху есть клетки - двигаемся влево, если справа есть клетки - двигаемся вверх конечно, это очень обобщенные условия, но думаю суть понятная 0

@MaxGlock 4 / 3 / 3 Регистрация: 21.03.2020 Сообщений: 19
	08.04.2020, 09:21 [ТС]
	codcw, спасибо за совет 0

@MaxGlock 4 / 3 / 3 Регистрация: 21.03.2020 Сообщений: 19
	08.04.2020, 12:44 [ТС]
	codcw, XD, ну ладно, сам дороботаю))) 0

@u235 5516 / 2869 / 571 Регистрация: 07.11.2019 Сообщений: 4,759
	08.04.2020, 19:19
	codcw, я, наверное, бы решил эту задачу как-то так: 1. перевел бы карту в бинарную матрицу. 0-, 1- # 2. Свертка с матрицей весов 3х3 (м.б. 2х2 тоже пойдет), типа [[1, 2,4],[8,16,32],[64,128,256]] В результате получившиеся значение будет кодировать локальное окружение точки. 3. Таблица подстановки, каждому полученному в п.2 значению ставится в соответствие 0 или 1. В итоге получаем контур. 4. Находим центр масс контура и переводим координаты контура в полярные из центра масс. 5. Сортируем список декартовых координат точек, используя ключ - полярный угол. 2 и 3 можно заменить эрозией и xor c исходной картой для выделения контура. (можно задействовать PIL)., м.б. это все также можно заменить на свертку с лапласианом. 1

@TarKovNet 0 / 0 / 0 Регистрация: 04.11.2021 Сообщений: 4
	09.12.2021, 16:08
	Кто-то может перевести это в С++. Заранее спасибо! 0