Условие на задачата:
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
MomchilAntonov avatar MomchilAntonov 2 Точки

Колеги, дайте едно читаво решение на тази задача. Направо ме съсипа :)

0
matani avatar matani 0 Точки

Колеги, мъча я таз' гад от два дни... положението е следното:

https://pastebin.com/675QXdQD

Но, искам да обърна внимание на ред 36, в който ред с проверки нарочно премахнах проверката х == 0, тоест, в този случай, проверка, която работи, ако Кейт е на първия ред на картата и може да излезе с един ход нагоре. Е, противно на всякаква логика с тази проверка - резултатът в Джъдж е 60/100, без нея 100/100.

Не знам, може би някъде нещо не е наред и съм омазал, но аз лично капитулирам и минавам нататък.  :)

0
leonidg avatar leonidg 0 Точки

Здравейте,

Началният ми подход беше като в първия пост, но се оказа адски трудно за дебъгване (поне за мен). Затова седнах и го разписах като първолак:

https://pastebin.com/TAEAfFNN

 

0
raogma avatar raogma 0 Точки

И аз я реших, като махнах проверката за редовете == 0. Според мен имат грешка с тестовете.

Аз ползвах рекурсия, тъй като става малко по - прегледно:

https://pastebin.com/WSV8Bxrt

0
Martinzca avatar Martinzca 11 Точки

И аз дълго време се лутах и получавах около 50 точки само и единствено, защото някак си бях приел, че само нагоре и надолу са възможни изходи :D. Тотално бях изключил за възможните изходи наляво и надясно.

Ето и моето решение:

nums = int(input())
kaze = []
for i in range(nums):
    kaze.append(input())

maze = []
moves = 0

for line in kaze:
    maze.append(list(''.join(line)))

height = len(maze)
width = len(maze[0])

def find_position(maze):
    for y in range(len(maze)):
        for x in range(len(maze[y])):
            if maze[y][x] == 'k':
                k = [y, x]
                if 0 <= y + 1 < height:
                    down = [y + 1, x]
                else:
                    down = False
                if 0 <= x - 1 < width:
                    left = [y, x - 1]
                else:
                    left = False
                if 0 <= x + 1 < width:
                    right = [y, x + 1]
                else:
                    right = False
                if 0 <= y - 1 < height:
                    up = [y - 1, x]
                else:
                    up = False

    return [k, down, left, right, up]


while True:
    k, down, left, right, up = find_position(maze)
    if left and maze[left[0]][left[1]] == ' ':
        maze[k[0]][k[1]] = '#'
        maze[left[0]][left[1]] = 'k'
        moves += 1
    elif right and maze[right[0]][right[1]] == ' ':
        maze[k[0]][k[1]] = '#'
        maze[right[0]][right[1]] = 'k'
        moves += 1
    elif down and maze[down[0]][down[1]] == ' ':
        maze[k[0]][k[1]] = '#'
        maze[down[0]][down[1]] = 'k'
        moves += 1
    elif up and maze[up[0]][up[1]] == ' ':
        maze[k[0]][k[1]] = '#'
        maze[up[0]][up[1]] = 'k'
        moves += 1
    elif k[0] == height - 1 or k[0] == 0 or k[1] == width - 1 or k[1] == 0:
        moves += 1
        print(f'Kate got out in {moves} moves')
        break
    else:
        print('Kate cannot get out')
        break

 

0