حل تمرین دومینوها کوئرا با پایتون

حل تمرین دومینوها کوئرا با پایتون

در این نوشته به روش حل یکی از سوالات پیاده‌سازی برنامه نویسی وب‌سایت کوئرا می‌پردازیم.

حل تمرین دومینوها کوئرا با پایتون

در هر خانه از یک جدول $n$ در m یک دومینوی ایستاده قرار داده شده است. هر دومینو یا عمودی است یا افقی (دومینوهای عمودی فقط در جهت بالا یا پایین می‌افتد و دومینوهای افقی فقط در جهت چپ یا راست). وقتی یک دومینو در یک جهت می‌افتد دومینوی موجود در خانه‌ی بعدی (در همان جهت) نیز اگر از نظر عمودی و افقی بودن مانند این دومینو شود می‌افتد (دومینوها فقط در شرایط گفته شده بر روی دومینوهای دیگر تاثیر می‌گذارند). می‌خواهیم تعدادی دومینو را بیاندازیم به طوری که همه‌ی دومینوها بیافتند. حداقل چند دومینو را باید بیاندازیم؟

ورودی

در خط اول ورودی دو عدد n و m آمده است که تعداد سطرها و ستون‌های جدول را نشان می‌دهند. در $n$ خط بعدی در هر خط، m کاراکتر آمده که هر کدام نشان دهنده‌ی وضعیت یک دومینو است (| برای دومینوهای افقی و – برای دومینوهای عمودی)

خروجی

جواب مسئله را در یک خط چاپ کنید.

مثال

ورودی نمونه 1

3 3
|||
||-
||-

خروجی نمونه 1

4

کد پایتون سوال تمرین دومینوها

def dfs(x, y, n, m, grid, visited):
    stack = [(x, y)]
    while stack:
        cx, cy = stack.pop()
        if visited[cx][cy]:
            continue
        visited[cx][cy] = True
        if grid[cx][cy] == '|':
            if cx + 1 < n and not visited[cx + 1][cy]:
                stack.append((cx + 1, cy))
            if cx - 1 >= 0 and not visited[cx - 1][cy]:
                stack.append((cx - 1, cy))
        else:
            if cy + 1 < m and not visited[cx][cy + 1]:
                stack.append((cx, cy + 1))
            if cy - 1 >= 0 and not visited[cx][cy - 1]:
                stack.append((cx, cy - 1))

def solve(n, m, grid):
    visited = [[False] * m for _ in range(n)]
    count = 0
    for i in range(n):
        for j in range(m):
            if not visited[i][j]:
                dfs(i, j, n, m, grid, visited)
                count += 1
    return count

n, m = map(int, input().split())
grid = [input().strip() for _ in range(n)]

result = solve(n, m, grid)
print(result)

منبع سوال: کوئرا

اگر نیاز به حل تمرین‌های دیگری از کوئرا دارید در بخش نظرات همین نوشته برای ما بنویسید.