Остров

@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

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

Новые блоги и статьи Все статьи Все блоги /
Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .
Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .

@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 5519 / 2872 / 571 Регистрация: 07.11.2019 Сообщений: 4,764
	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