Sam the eligible bachelor

Added: 2025-09-13 04:48:07

Question Image

Sam the eligible bachelor

Answer

✏️ Edit
from collections import deque

def bride_hunt(matrix):
    n = len(matrix)
    m = len(matrix[0])
    dirs = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
    dist = [[-1]*m for _ in range(n)]
    q = deque([(0,0)])
    dist[0][0] = 0
    
    while q:
        x,y = q.popleft()
        for dx,dy in dirs:
            nx, ny = x+dx, y+dy
            if 0 <= nx < n and 0 <= ny < m and dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx,ny))
    
    brides = []
    for i in range(n):
        for j in range(m):
            if matrix[i][j] == 1 and not (i==0 and j==0):
                qualities = 0
                for dx,dy in dirs:
                    ni, nj = i+dx, j+dy
                    if 0 <= ni < n and 0 <= nj < m and matrix[ni][nj] != 0:
                        if not (ni==0 and nj==0):
                            qualities += 1
                if qualities > 0:
                    brides.append((qualities, dist[i][j], i+1, j+1))
    
    if not brides:
        return "No suitable girl found"
    
    max_q = max(b[0] for b in brides)
    candidates = [b for b in brides if b[0] == max_q]
    min_d = min(b[1] for b in candidates)
    final = [b for b in candidates if b[1] == min_d]
    
    if len(final) > 1:
        return "Polygamy not allowed"
    
    q, d, r, c = final[0]
    return f"{r}:{c}:{q}"

n,m = map(int,input().split())
matrix = [list(map(int,input().split())) for _ in range(n)]
print(bride_hunt(matrix))