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