Остров

@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

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

Новые блоги и статьи Все статьи Все блоги /
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .

@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

Опции темы