Форум сайта python.su
Добрый день. Долго мучаюсь над задачей(поиск не дал результата, точнее дал, но он увы неправильный(код не проходит тесты))
____
Прямоугольный садовый участок шириной 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()
Офлайн
мне кажется или условие неполное или нужно найти все возможные сочетания?
#.#.#.#.#.
.#.#.#.#.#
#.#.#.#.#.
.#.#.#.#.#
#.#.#.#.#.
Офлайн
izekia
мне кажется или условие неполное или нужно найти все возможные сочетания?
В первой строке находятся числа N и M через пробел, далее идут N строк по M символов. Символ # обозначает территорию грядки, точка соответствует незанятой территории. Других символов нет. (1 ≤ N, M ≤ 200)
Отредактировано valoroso (Ноя. 14, 2016 14:55:36)
Офлайн
самая простая идея такова:
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)
Отредактировано izekia (Ноя. 14, 2016 15:06:27)
Офлайн
izekiaк несчастью код не прошел проверку
самая простая идея такова:
case1 = ['##..#####.',
'.#.#.#....',
'###..##.#.',
'..##.....#',
'.###.#####']
Офлайн
да, точно … у меня там изгибов не было
Офлайн
немного громоздко получилось, но сейчас ничего лучше не придумалось:
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))
Офлайн
izekiaу самого голова пухнет. ни мой ни твой код не проходит все тесты на:
немного громоздко получилось, но сейчас ничего лучше не придумалось:
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)
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.
Прикреплённый файлы: fail_1.jpg (87,9 KБ)
Офлайн
по скорости не проходит?
Офлайн
izekiaзакинул еще на https://acmp.ru/?main=task&id_task=432
по скорости не проходит?
-Runtime error.
-Ошибка исполнения. Программа завершила работу с ненулевым кодом возврата. В этом случае результат работы не проверяется.
-Возможно, в программе произошло обращение к несуществующему элементу массива, деление на ноль и т.д. Возможно, программа на C++ не завершается оператором "return 0" или по иной причине вернула ненулевой код возврата.
Отредактировано valoroso (Ноя. 14, 2016 17:16:48)
Офлайн