Уведомления

Группа в Telegram: @pythonsu

#1 Ноя. 14, 2016 14:20:40

valoroso
Зарегистрирован: 2016-11-14
Сообщения: 14
Репутация: +  0  -
Профиль   Отправить e-mail  

Обход в глубину

Добрый день. Долго мучаюсь над задачей(поиск не дал результата, точнее дал, но он увы неправильный(код не проходит тесты))
____

Прямоугольный садовый участок шириной N и длиной M метров разбит на квадраты со стороной 1 метр.
На этом участке вскопаны грядки. Грядкой называется совокупность квадратов, удовлетворяющая
таким условиям:

из любого квадрата этой грядки можно попасть в любой другой квадрат этой же грядки,
последовательно переходя по грядке из квадрата в квадрат через их общую сторону;
никакие две грядки не пересекаются и не касаются друг друга ни по вертикальной,
ни по горизонтальной сторонам квадратов (касание грядок углами квадратов допускается).
Подсчитайте количество грядок на садовом участке.

Входные данные:
5 10
##......#.
.#..#...#.
.###....#.
..##....#.
........#.

Дополнительные модули не использовать.
——————-
По мне, самый простой вариант: просмотреть массив и выделить все номера грядок в отдельный лист.
А потом проверить все элементы нового листа на горизонтальную и вертикальную смежность.
Но с последним проблема - Питон учу вторую неделю…

 n, m = map(int, input().split()) 
fields = [ list(input()) for _ in range(n) ]
 
beds = 0
ex = []
count = []
 
for x in range(n):
    for y in range(m):
        if fields[x][y] == '#':
            ex.append((x,y))
ex.sort()

Офлайн

#2 Ноя. 14, 2016 14:26:34

izekia
От:
Зарегистрирован: 2008-07-19
Сообщения: 317
Репутация: +  12  -
Профиль   Отправить e-mail  

Обход в глубину

мне кажется или условие неполное или нужно найти все возможные сочетания?

#.#.#.#.#.
.#.#.#.#.#
#.#.#.#.#.
.#.#.#.#.#
#.#.#.#.#.



Офлайн

#3 Ноя. 14, 2016 14:48:45

valoroso
Зарегистрирован: 2016-11-14
Сообщения: 14
Репутация: +  0  -
Профиль   Отправить e-mail  

Обход в глубину

izekia
мне кажется или условие неполное или нужно найти все возможные сочетания?

написал полный текст задачи, единственное что можно добавить:
В первой строке находятся числа N и M через пробел, далее идут N строк по M символов. Символ # обозначает территорию грядки, точка соответствует незанятой территории. Других символов нет. (1 ≤ N, M ≤ 200)
надо найти количество стоящих смежно одинаковых элементов в матрице.

насколько понял, надо обходить массив,помечая просмотренные. найденные номера грядок('#') записывать в стек и заменять в оригинальном массиве на землю('.').
Нашел грядку - смежные элементы просмотрел, пока на землю не наткнулся. Количество грядок на 1 увеличил, стек обнулил и дальше по массиву пошел. Но вот нормальную реализацию пока не сделал…

Отредактировано valoroso (Ноя. 14, 2016 14:55:36)

Офлайн

#4 Ноя. 14, 2016 15:03:23

izekia
От:
Зарегистрирован: 2008-07-19
Сообщения: 317
Репутация: +  12  -
Профиль   Отправить e-mail  

Обход в глубину

самая простая идея такова:

 case1 = ['##......#.',
         '.#..#...#.',
         '.###....#.',
         '..##....#.',
         '........#.']
N, M = 5, 10
c = 0
for i in range(N):
    for j in range(M):
        if case1[i][j] == '#' and (i == 0 or case1[i-1][j] == '.') and (j == 0 or case1[i][j-1] == '.'):
            c += 1
print(c)
3

на самом деле можно прыгать через клетку если нашли грядку, но наверное этого хватит



Отредактировано izekia (Ноя. 14, 2016 15:06:27)

Офлайн

#5 Ноя. 14, 2016 15:15:52

valoroso
Зарегистрирован: 2016-11-14
Сообщения: 14
Репутация: +  0  -
Профиль   Отправить e-mail  

Обход в глубину

izekia
самая простая идея такова:
к несчастью код не прошел проверку временем тестом
если взять другие входные данные
 
case1 = ['##..#####.',
'.#.#.#....',
'###..##.#.',
'..##.....#',
'.###.#####']
то уже ошибка - 8 вместо 5

Офлайн

#6 Ноя. 14, 2016 15:24:23

izekia
От:
Зарегистрирован: 2008-07-19
Сообщения: 317
Репутация: +  12  -
Профиль   Отправить e-mail  

Обход в глубину

да, точно … у меня там изгибов не было



Офлайн

#7 Ноя. 14, 2016 16:18:12

izekia
От:
Зарегистрирован: 2008-07-19
Сообщения: 317
Репутация: +  12  -
Профиль   Отправить e-mail  

Обход в глубину

немного громоздко получилось, но сейчас ничего лучше не придумалось:

 case1 = ['##..#####.',
         '.#.#.#....',
         '###..##.#.',
         '..##.....#',
         '.###.#####']
  
case2 = ['##......#.',
         '.#..#...#.',
         '.###....#.',
         '..##....#.',
         '........#.']
  
case3 = ['#.#.#.#.#.',
         '.#.#.#.#.#',
         '#.#.#.#.#.',
         '.#.#.#.#.#',
         '#.#.#.#.#.']
  
case4 = ['..........',
         '..........',
         '..........',
         '..........',
         '..........']
case5 = ['##########',
         '##########',
         '##########',
         '##########',
         '##########']
  
case6 = ['##########',
         '.#.#.#.#.#',
         '##########',
         '#.#.#.#.#.',
         '##########']
  
def solve(N, M, case):
    result = 0
    get_cell_num = lambda i, j: i + j * N
    unknown_cells = set(range(N * M))
      
    def check_cell(i, j, check_cell_num = True):
        if check_cell_num:
            cell_num = get_cell_num(i, j)
            try:
                unknown_cells.remove(cell_num)
            except KeyError:
                return False
        if case[i][j] == '#':
            if i > 0:
                check_cell(i - 1, j)
            if i < N - 1:
                check_cell(i + 1, j)
            if j > 0:
                check_cell(i, j - 1)
            if j < M - 1:
                check_cell(i, j + 1)
        else:
            return False
        return True
      
    while unknown_cells:
        cell_num = unknown_cells.pop()
        j, i = divmod(cell_num, N)
        if check_cell(i, j, False):
            result += 1
    return result        
      
print(solve(5, 10, case1))
print(solve(5, 10, case2))
print(solve(5, 10, case3))    
print(solve(5, 10, case4))
print(solve(5, 10, case5))
print(solve(5, 10, case6))

5
3
25
0
1
1



Офлайн

#8 Ноя. 14, 2016 16:57:39

valoroso
Зарегистрирован: 2016-11-14
Сообщения: 14
Репутация: +  0  -
Профиль   Отправить e-mail  

Обход в глубину

izekia
немного громоздко получилось, но сейчас ничего лучше не придумалось:
у самого голова пухнет. ни мой ни твой код не проходит все тесты на:
https://www.e-olymp.com/ru/problems/1065
твой сделал - 7 из 12
моя лучшая попытка - 11 из 12
try:
n, m = input().split()
n = int(n)
m = int(m)
alll = [[] for i in range(n)]
visited = [[False for j in range(m)] for i in range(n)]
num = 0

for i in range(n):
row = list(input())
for j in range(m):
alll[i].append(row[j])

def dfs(x, y):
visited[x][y] = True
for dx, dy in [[-1, 0], [0, -1], [0, 1], [1, 0]]:
if 0 <= x + dx <= n-1 and 0 <= y + dy <= m-1:
if alll[x + dx][y + dy] == "#" and not visited[x + dx][y + dy]:
dfs(x + dx, y + dy)

for x in range(n):
for y in range(m):
if alll[x][y] == "#" and not visited[x][y]:
dfs(x, y)
num += 1
except Exception:
num += 1

print(num)
f
а вот паскаль 12 из 12
var g:array [1..200,1..200] of char; k,i,j,n,m:integer;
procedure dfs(x,y:longint);
begin
g[x,y]:='o';
if (y<m )and(g[x,y+1]='#') then dfs(x,y+1);
if (y>1 )and(g[x,y-1]='#') then dfs(x,y-1);
if (x<n )and(g[x+1,y]='#') then dfs(x+1,y);
if (x>1 )and(g[x-1,y]='#') then dfs(x-1,y);
end;
begin
readln(n,m);
k:=0;
for i:=1 to n do begin
for j:=1 to m do
read(g[i,j]);
readln;
end;
for i:=1 to n do
for j:=1 to m do begin
if (g[i,j]='#')
then begin
k:=k+1;
dfs(i,j);
end;
end;
writeln(k);
end.

причем по скорости, память - Паскаль - 3.89 ms/693 KiB
Питон твой - 67.91 ms/7984, мой - 46.92 ms/6362

Прикреплённый файлы:
attachment fail_1.jpg (87,9 KБ)

Офлайн

#9 Ноя. 14, 2016 17:04:10

izekia
От:
Зарегистрирован: 2008-07-19
Сообщения: 317
Репутация: +  12  -
Профиль   Отправить e-mail  

Обход в глубину

по скорости не проходит?



Офлайн

#10 Ноя. 14, 2016 17:14:46

valoroso
Зарегистрирован: 2016-11-14
Сообщения: 14
Репутация: +  0  -
Профиль   Отправить e-mail  

Обход в глубину

izekia
по скорости не проходит?
закинул еще на https://acmp.ru/?main=task&id_task=432
там дало:

-Runtime error.

-Ошибка исполнения. Программа завершила работу с ненулевым кодом возврата. В этом случае результат работы не проверяется.

-Возможно, в программе произошло обращение к несуществующему элементу массива, деление на ноль и т.д. Возможно, программа на C++ не завершается оператором "return 0" или по иной причине вернула ненулевой код возврата.


Проблема, в том, что они не пишут, по каким тестам гоняют, а просто ставят перед фактом.

Отредактировано valoroso (Ноя. 14, 2016 17:16:48)

Офлайн

Board footer

Модераторировать

Powered by DjangoBB

Lo-Fi Version