Крест

@utsushi · Регистрация: 27.04.2024

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

У нас есть сетка с H строками и W столбцами. Мы обозначаем ячейку в i-й строке сверху и j-м столбце слева сетки как (i,j). Каждая ячейка в сетке имеет символ ‘#’ или ‘.’, написанный в ней. Пусть C[i][j] — символ, написанный в ячейке (i,j). Для целых чисел i и j, при которых хотя бы одно из условий 1≤ileH и 1≤j≤W нарушается, мы определяем C[i][j] как ‘.’ (другими словами, все пространство вне сетки заполнено точками).

Рассмотрим некоторую клетку (a,b). Будем говорить, что клетка (a,b) является центром креста размера n, если выполняются все следующие условия:
C[a][b] равен ‘#’.
C[a+d][b+d], C[a+d][b−d], C[a−d][b+d], и C[a−d][b−d] равны ‘#’, для всех целых чисел d таких, что 1≤d≤n.

Хотя бы один из C[a+n+1][b+n+1], C[a+n+1][b−n−1], C[a−n−1][b+n+1], и C[a−n−1][b−n−1] равен ‘.’.

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

Пусть N=min(H,W), и Sn будет числом крестов размера n. Найдите S1, S2, ..., SN.

Формат входных данных
В первой строке даны целые числа H и W (3≤H,W≤100).

Далее идут H строк, содержащих по W символов ‘#’ и ‘.’, задающие сетку C.

Формат результата
Выведите
S1, S2, ..., SN, разделенные пробелами.

Примеры
Входные данные
5 9
#.#.#...#
.#...#.#.
#.#...#..
.....#.#.
....#...#
Результат работы
1 1 0 0 0
Входные данные
3 3
...
...
...
Результат работы
0 0 0
Входные данные
3 16
#.#.....#.#..#.#
.#.......#....#.
#.#.....#.#..#.#
Результат работы
3 0 0

Тема Линейный поиск в списках и матрицах

@anton7685 · 10.05.2024, 18:58

Присоединяюсь к теме. Cам не могу решить

Добавлено через 2 часа 17 минут
Я делал так но программа выводит не то, что нужно.

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
def check_cross(grid, r, c, size):
    if grid[r][c] != "#":
        return False
    for d in range(1, size+1):
        if (r+d >= len(grid) or c+d >= len(grid[0]) or c-d < 0 or r-d < 0):
            return False
        if grid[r+d][c+d] != "#" or grid[r+d][c-d] != "#" or grid[r-d][c+d] != "#" or grid[r-d][c-d] != "#":
            return False
    if r+size >= len(grid) or c+size >= len(grid[0]) or c-size < 0 or r-size < 0:
        return False
    if grid[r+size][c+size] == "." or grid[r+size][c-size] == "." or grid[r-size][c+size] == "." or grid[r-size][c-size] == ".":
        return True
    return False
 
H, W = map(int, input().split())
grid = []
for _ in range(H):
    grid.append(input())
 
result = [0] * min(H, W)
 
for r in range(H):
    for c in range(W):
        for size in range(1, min(H, W) + 1):
            if check_cross(grid, r, c, size):
                result[size-1] += 1
 
print(*result)

Добавлено через 3 часа 21 минуту
моя программа выводит 0 0 0 0 0 а не 1 1 0 0 0

@idealist · 10.05.2024, 20:36

А интересно, такая матрица возможна или нет:

Python
1
2
3
4
#.#.#.#
.##.##.
#.###.#
..#.#..

@anton7685 · 10.05.2024, 21:02

idealist, Да существует. Она удовлетворяет условиям задачи

@contrlc · 10.05.2024, 21:41

Python
1
2
3
4
5
6
7
8
9
10
11
12
h, w = map(int, input().split())
grid, n = [input() for _ in range(h)], min(h, w)
s = [0] * n
 
for size in range(1, n + 1):
    for i in range(size, h - size):
        for j in range(size, w - size):
            if grid[i][j] == '#' and all(grid[i + dx][j + dy] == '#' for d in range(1, size + 1) for dx, dy in [(d, d), (d, -d), (-d, d), (-d, -d)]):
                if any((i + dx >= h or j + dy >= w or i + dx < 0 or j + dy < 0 or grid[i + dx][j + dy] == '.')
                    for dx, dy in [(size + 1, size + 1), (size + 1, -size - 1), (-size - 1, size + 1), (-size - 1, -size - 1)]):
                    s[size - 1] += 1
print(*s)

@anton7685 · 10.05.2024, 21:43

contrlc, от всей души Благодарю вас!! Всё верно

@idealist · 10.05.2024, 22:10

Ну, так можно:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from collections import Counter
 
def get_cross(matr, i, j):
    res = 0
    CROSS_SYMB = '#'
    if matr[i][j] != CROSS_SYMB:
        return 0
    d = 1
    while (i-d >= 0 and i+d < h and j-d >= 0 and j+d < w
           and matr[i-d][j-d: j+d+1: d*2] == matr[i+d][j-d: j+d+1: d*2] == CROSS_SYMB * 2):
        res = d
        d += 1
    return res
 
h,w = map(int, input('n, m->').split())
matr = [input('->') for _ in range(h)]
cc = Counter()
for i in range(h):
    for j in range(w):
        cc[get_cross(matr, i, j)] += 1
res = [cc[i] for i in range(1, min(h,w)+1)]
print(*res)

@idealist · 11.05.2024, 05:53

Подсократил немного:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from collections import Counter
 
def get_cross(matr, i, j):
    CROSS_SYMB = '#'
    if matr[i][j] != CROSS_SYMB:
        return 0
    for d in range(1, min(len(matr), len(matr[0]))):
        if not (i-d >= 0 and i+d < h and j-d >= 0 and j+d < w
            and matr[i-d][j-d: j+d+1: d*2] == matr[i+d][j-d: j+d+1: d*2] == CROSS_SYMB * 2):
            return d-1
 
h,w = map(int, input('n, m->').split())
matr = [input('->') for _ in range(h)]
cc = Counter()
for i in range(h):
    for j in range(w):
        cc[get_cross(matr, i, j)] += 1
res = [cc[i] for i in range(1, min(h,w)+1)]
print(*res)

Новые блоги и статьи Все статьи Все блоги /
Подстановка значения реквизита справочника в табличную часть документа 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. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .
Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .

@utsushi 207 / 5 / 2 Регистрация: 27.04.2024 Сообщений: 72

	Крест 07.05.2024, 13:59. Показов 1361. Ответов 7 Метки нет (Все метки) У нас есть сетка с H строками и W столбцами. Мы обозначаем ячейку в i-й строке сверху и j-м столбце слева сетки как (i,j). Каждая ячейка в сетке имеет символ ‘#’ или ‘.’, написанный в ней. Пусть C[i][j] — символ, написанный в ячейке (i,j). Для целых чисел i и j, при которых хотя бы одно из условий 1≤ileH и 1≤j≤W нарушается, мы определяем C[i][j] как ‘.’ (другими словами, все пространство вне сетки заполнено точками). Рассмотрим некоторую клетку (a,b). Будем говорить, что клетка (a,b) является центром креста размера n, если выполняются все следующие условия: C[a][b] равен ‘#’. C[a+d][b+d], C[a+d][b−d], C[a−d][b+d], и C[a−d][b−d] равны ‘#’, для всех целых чисел d таких, что 1≤d≤n. Хотя бы один из C[a+n+1][b+n+1], C[a+n+1][b−n−1], C[a−n−1][b+n+1], и C[a−n−1][b−n−1] равен ‘.’. Сетка имеет несколько крестов. В ячейках, за исключением тех, которые содержат крест, не пишется #. Кроме того, никакие две ячейки, принадлежащие двум разным крестам, не имеют общего угла. Пусть N=min(H,W), и Sn будет числом крестов размера n. Найдите S1, S2, ..., SN. Формат входных данных В первой строке даны целые числа H и W (3≤H,W≤100). Далее идут H строк, содержащих по W символов ‘#’ и ‘.’, задающие сетку C. Формат результата Выведите S1, S2, ..., SN, разделенные пробелами. Примеры Входные данные 5 9 #.#.#...# .#...#.#. #.#...#.. .....#.#. ....#...# Результат работы 1 1 0 0 0 Входные данные 3 3 ... ... ... Результат работы 0 0 0 Входные данные 3 16 #.#.....#.#..#.# .#.......#....#. #.#.....#.#..#.# Результат работы 3 0 0 Тема Линейный поиск в списках и матрицах 0

@anton7685 190 / 3 / 2 Регистрация: 08.05.2024 Сообщений: 24
	10.05.2024, 21:02
	idealist, Да существует. Она удовлетворяет условиям задачи 0

@anton7685 190 / 3 / 2 Регистрация: 08.05.2024 Сообщений: 24
	10.05.2024, 21:43
	contrlc, от всей души Благодарю вас!! Всё верно 0