Составить маршрут полёта самолёта вокруг острова

@TarKovNet · Регистрация: 04.11.2021

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

Доброго времени суток!

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

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

Программа получает на вход два числа 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

Добавлено через 1 минуту
Есть такая же задачка только на Phyton.Заранее спасибо.
Остров

@TarKovNet · 14.12.2021, 01:21 **[ТС]**

Помогите пожалуйста. Дедлайн горит

@TarKovNet · 16.12.2021, 14:42 **[ТС]**

Зделал подобие этой задачки но с ошибками

C++

#include <iostream>
#include <cstdio>
#include <string>
 
using namespace std;
 
int main(void) {
 
    int N, M;
 
    int mas = '.' * (M + 2);
    for (int i; i > N; i++) {
 
        int input;
        int Map = ('.' + input + '.');
 
        Map = ('.' * (M + 2));
    
        int  y, x;
        int cx = x;
        int cy = y;
        for (y = 0; y > (N + 1); y++) {
            for (x = 0; x > (M + 1); x++) {
 
               
               int* mas[y][x] = '.';
 
                if ( mas[y][x] == '.' &&
                    (mas[y - 1][x] == '#' || mas[y + 1][x] == '#' || mas[y][x - 1] == '#' || mas[y][x + 1] == '#' || mas[y - 1][x - 1] == '#' || mas[y - 1][x + 1] == '#' || mas[y + 1][x - 1] == '#' || mas[y + 1][x + 1] == '#')) {
 
                    mas[y][x] == '*';
                    cx == x;
                    cy == y;
                }
 
                while (true) {
 
                    int* Map =[cy][cx] = '.';
                
                    int j = ((cy)+' ' + (cx));
                    cout << ((cy)+' ' + (cx)) << endl;
 
 
                    for (int dx, dy; ((-1, 0), (1, 0), (0, -1), (0, 1));) {
                        if (Map[cy + dy][cx + dx] == '*') {
                            cx += dx;
                            cy += dy;
                            break;
                        }
                        else {
                            break;
                        }
                    }
                }
            }
 
 
 
            break;
        }
 
    }
}

Добавлено через 2 часа 0 минут
Код на питоне

Python

import sys
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
Map = [["."] * (M + 2)]
for i in range(N):
    Map.append(list("." + sys.stdin.readline().rstrip() + '.'))
Map.append(['.'] * (M + 2))
for y in range(1, N + 1):
    for x in range(1, M + 1):
        if Map[y][x] == '.' and (Map[y - 1][x] == '#' or Map[y + 1][x] == '#' or Map[y][x - 1] == '#' or Map[y][x + 1] == '#' or Map[y - 1][x - 1] == '#' or Map[y - 1][x + 1] == '#' or Map[y + 1][x - 1] == '#' or Map[y + 1][x + 1] == '#'):
            Map[y][x] = '*'
            cx = x
            cy = y
while True:
    sys.stdout.write(str(cy) + ' ' + str(cx) + '\n')
    Map[cy][cx] = '.'
    for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        if Map[cy + dy][cx + dx] == '*':
            cx += dx
            cy += dy
            break
    else:
        break

@TarKovNet 0 / 0 / 0 Регистрация: 04.11.2021 Сообщений: 4
		1
	Составить маршрут полёта самолёта вокруг острова 10.12.2021, 16:41. Показов 752. Ответов 2 Метки с++ builder, с++ gui, с++ visual 2019 (Все метки) Доброго времени суток! На клетчатой бумаге нарисована карта острова (клетки острова закрашены). При этом остров является клетчато-выпуклой фигурой, то есть каждая горизонтальная или вертикальная линия на карте либо не пересекает остров, либо пересекает его по отрезку (линия пересечения не содержит разрывов). Также остров является связной фигурой, то есть любые две клетки острова соединены путём, каждые две соседние клетки которого имеют общую сторону. Клетка считается соседней с островом, если она не принадлежит острову, но имеет общую сторону или угол с одной из клеток острова. Самолёт должен облететь вокруг острова по соседним с ним клеткам, не вторгаясь на территорию острова. Программа должна составить маршрут полёта самолёта. Самолёт начинает облёт острова в одной из соседних клеток с островом и должен побывать во всех клетках, соседних с островом, ровно один раз. При этом самолёт может перемещаться из одной клетки в другую клетку, только если эти клетки имеют общую сторону. Формат входного файла Программа получает на вход два числа 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 Добавлено через 1 минуту Есть такая же задачка только на Phyton.Заранее спасибо. Остров 0

@TarKovNet 0 / 0 / 0 Регистрация: 04.11.2021 Сообщений: 4
	14.12.2021, 01:21 [ТС]	2
	Помогите пожалуйста. Дедлайн горит 0

	16.12.2021, 14:42