Loading...
andrey_bg avatar andrey_bg 4 Точки

Lists Advanced - More Exercises/ 05. Kate's Way Out

Здравейте колеги,

имам проблем с това лабиринтче-въртя суча и не мога повече от 60/100 точки да изкарам, като ми гърми с runtime error на 3-ти и 4-ти опит, а при първото си решение 4-ти ми беше верен, така че предполагам че някои гранични случаи пропускам.

Ще бъда благодарен ако някой може да ми помогне! smiley

 

Условие на задачата:

4.Kate's Way Out

Kate is stuck into a maze, you have to help her to find her way out

On the first line you will be given how many rows there are in the maze. On the next n lines you will be given the maze itself. Here is a legend for the maze:

  • "#" - means a wall; Kate cannot go through there
  • " " - means empty space; Kate can go through there
  • "k" - the initial position of Kate; start looking for a way out from there

There are two options: Kate either gets out or not. If Kate can get out print the following:
"Kate got out in {number_of_moves} moves". Otherwise print: "Kate cannot get out"

Examples

Input

Output

4

######

##  k#

## ###

## ###

Kate got out in 5 moves

5

######

##  k#

## ###

######

## ###

Kate cannot get out

Моето решение: 

rows=int(input())
maze=[list(input()) for i in range(rows)]
start=[(row,col) for row in range(rows) for col in range(len(maze[row])) if maze[row][col]=="k"][0]

exitPoint=[(row,col) for row in range(rows) for col in range(len(maze[row])) if maze[row][col]==" " and
           (row==rows-1 or row==0 or col==0 or col==len(maze[1])-1)][0]
washere=[]; correctPath=[]

for row in range(rows):
    washere.append([])
    correctPath.append([])
    for col in range(len(maze[row])):
        washere[row].append(False)
        correctPath[row].append(False)


def recursiveSolve(x, y):
    if x == exitPoint[0] and y== exitPoint[1]: return True  #If you reached the end
    elif maze[x][y] == "#" or washere[x][y]: return False   #If you are on a wall or already were here

    # mark as visited
    washere[x][y]=True

    if x != 0: # Checks if not on top edge
        if recursiveSolve(x - 1, y): # Recalls method one up
            correctPath[x][y] = True # Sets that path value to True;
            return True

    if x != rows  - 1: # Checks if not on bottom edge
        if recursiveSolve(x+1, y): # Recalls method one down
            correctPath[x][y] = True
            return True

    if y != 0: # Checks if not on left edge
        if recursiveSolve(x, y-1): # Recalls method one to the left
            correctPath[x][y] = True
            return True
    if y != len(maze[x]) - 1: # Checks if not on right edge
        if recursiveSolve(x, y+1): # Recalls method one to the right
            correctPath[x][y] = True
            return True
    return False;

counter=1
res=recursiveSolve(start[0],start[1])
counter+=sum(sum(row) for row in correctPath)
if not res:
    print("Kate cannot get out")
else:
    print(f"Kate got out in {counter} moves")
0
Fundamentals Module 22/02/2020 13:22:16
valerielashvili avatar valerielashvili 26 Точки

Здравейте,

Според мене тази задачка не е за начинаещи и би трябвало да се разглежда отделно в курса по алгоритми. Дори и да не е сложна за схващане тя изисква прилагане на определени подходи и DFS алгоритма за разрешаването й.

Ето едно примерно решение, което дава 100/100 точки използвайки Depht-First Search алгоритма за намиране на най-дългия път:

# This solution uses Depth-First Search algorithm

# An exit is any open space on the maze boundary
def is_exit(r, c, rows, cols):
    return (r == 0 or r == rows - 1 or c == 0 or c == cols - 1)

# Explore open cells in the maze using recursion
def find_way_out(row, col, grid, visited):
    rows = len(grid)
    cols = len(grid[0])

    # Mark current cell as visited
    visited.add((row, col))

    # Check if current cell is an exit
    found_exit = is_exit(row, col, rows, cols)
    max_move = 0

    # Explore neighbour cells in 4 directions
    for d_row, d_col in [(-1,0), (1,0), (0,-1), (0,1)]:
        new_r, new_c = row + d_row, col + d_col

        # Check boundaries, not visited, and not a wall
        if (0 <= new_r < rows and 0 <= new_c < cols and 
            (new_r, new_c) not in visited and grid[new_r][new_c] == ' '):

            exit_found, move = find_way_out(new_r, new_c, grid, visited)

            if exit_found:
                found_exit = True
                if move > max_move:
                    max_move = move
    
    visited.remove((row, col))

    # Return length including current cell
    return found_exit, max_move + 1

# Input
n_rows = int(input())
maze = []
wall = False

for _ in range(n_rows):
    maze.append(input())

# Find Kate's starting position
for i, row in enumerate(maze):
    if 'k' in row:
        start_row, start_col = i, row.index('k')
        break

visited_cells = set()
exit_found, move_count = find_way_out(start_row, start_col, maze, visited_cells)

# Output
if exit_found:
    print(f"Kate got out in {move_count} moves")
else:
    print("Kate cannot get out")

 

0
14/10/2025 19:32:47
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.