حل تمرین مربع مارپیج کوئرا با پایتون

حل تمرین مربع مارپیج کوئرا با پایتون

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

حل تمرین مربع مارپیج کوئرا با پایتون

کیان داخل یک اتاق گیر افتاده است و جایی را نمی‌بیند. می‌دانیم کف این اتاق مربع شکل با n×n کاشی مربع شکل کاشی کاری شده است. هم‌چنین هر کاشی شماره‌ای یکتا دارد و شماره گذاری کاشی‌ها به شکل مارپیچ است. برای مثال شکل زیر شماره گذاری کاشی‌ها برای n=5 را نشان می‌دهد.

کیان می‌داند یک شمع داخل این اتاق وجود دارد و می‌خواهد به آن برسد اما چون اتاق تاریک است جایی را نمی‌بیند. او از شما می‌خواهد که با گرفتن شماره کاشی‌ای که کیان روی آن ایستاده است و کاشی‌ای که شمع روی آن قرار دارد، او را راهنمایی کنید که چقدر باید در هر جهت حرکت کند تا به شمع برسد.

ورودی

در تنها خط ورودی به ترتیب سه عدد n و s و d با فاصله می‌آیند که طول اتاق، شماره‌ی کاشی کیان و شماره کاشی‌ای که شمع روی آن قرار دارد هستند.

خروجی

در اولین خط خروجی، یک عدد و یک کاراکتر با فاصله می‌آیند. عددی که چاپ می‌شود مقداری است که کیان باید در جهت افقی جابجا شود و اگر باید به سمت چپ برود کاراکتر برابر L و اگر باید به راست برود کاراکتر برابر R خواهد بود. اگر کیان نباید در جهت افقی جابجا شود، از این خط صرف نظر می‌شود. در دومین خط خروجی، یک عدد و یک کاراکتر با فاصله می‌آیند. عددی که چاپ می‌شود مقداری است که کیان باید در جهت عمودی جابجا شود و اگر باید به سمت بالا برود کاراکتر برابر U و اگر باید به پایین برود کاراکتر برابر D خواهد بود. اگر کیان نباید در جهت عمودی جابجا شود، از این خط صرف نظر می‌شود.

مثال

ورودی نمونه 1

5 1 25

خروجی نمونه 1

2 R
2 U

ورودی نمونه 2

5 3 22

خروجی نمونه 2

3 U

ورودی نمونه 3

15 67 24

خروجی نمونه 3

3 R
8 U

کد پایتون سوال تمرین مربع مارپیچ

def generate_spiral_matrix(n):
    matrix = [[0] * n for _ in range(n)]
    num = 1
    left, right, top, bottom = 0, n - 1, 0, n - 1
    while left <= right and top <= bottom:
        for i in range(left, right + 1):
            matrix[bottom][i] = num
            num += 1
        bottom -= 1
        for i in range(bottom, top - 1, -1):
            matrix[i][right] = num
            num += 1
        right -= 1
        for i in range(right, left - 1, -1):
            matrix[top][i] = num
            num += 1
        top += 1
        for i in range(top, bottom + 1):
            matrix[i][left] = num
            num += 1
        left += 1
    return matrix

def find_position(matrix, target):
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            if matrix[i][j] == target:
                return i, j
    return None

def main():
    import sys
    input = sys.stdin.read().strip()
    n, s, d = map(int, input.split())
    
    matrix = generate_spiral_matrix(n)
    s_row, s_col = find_position(matrix, s)
    d_row, d_col = find_position(matrix, d)
    
    if s_col != d_col:
        if d_col > s_col:
            print(f"{d_col - s_col} R")
        else:
            print(f"{s_col - d_col} L")
    
    if s_row != d_row:
        if d_row > s_row:
            print(f"{d_row - s_row} D")
        else:
            print(f"{s_row - d_row} U")

if __name__ == "__main__":
    main()

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

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