[Mock] Amazon 15 (다시보기)

마존아 어제 좋았잖아...☆

---

505. The Maze II

There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up, down, left or right, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.

Given the ball's start position, the destination and the maze, find the shortest distance for the ball to stop at the destination. The distance is defined by the number of empty spaces traveled by the ball from the start position (excluded) to the destination (included). If the ball cannot stop at the destination, return -1.

The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The start and destination coordinates are represented by row and column indexes.

My Answer 1: Wrong Answer (7% 통과)

class Solution:
    """
    @param maze: the maze
    @param start: the start
    @param destination: the destination
    @return: the shortest distance for the ball to stop at the destination
    """
    def shortestDistance(self, maze, start, destination):
        # write your code here
        def func(i, j, cnt):
            if i == destination[0] and j == destination[1]:
                self.ans = cnt
                return
            
            maze[i][j] = 2

            if i > 0 and maze[i-1][j] == 0:
                func(i-1, j, cnt+1)
            if i < len(maze)-1 and maze[i+1][j] == 0:
                func(i+1, j, cnt+1)
            if j > 0 and maze[i][j-1] == 0:
                func(i, j-1, cnt+1)
            if j < len(maze[0])-1 and maze[i][j+1] == 0:
                func(i, j+1, cnt+1)
            
            maze[i][j] = 0
        
        self.ans = 0
        func(start[0], start[1], 0)

        return self.ans

lintcode 야 고맙다...
https://www.lintcode.com/problem/788/description

if the ball cannot stop at the destination, return -1. 경우 처리가 안됨

다른 아이디어는..
start 에서만 사방을 보고 나머지는 한 방향으로만 계속 가도록 하기
계속 가다가 막다른 길에 도착하면 그 지점이 start 가 되기
이걸 반복하면 되지 않을까 했는데.. 구현을 못했읍니다..^^

Solution 1: Accepted (Runtime: 81 ms / Memory Usage: 5.51 MB)

import heapq

class Solution:
    """
    @param maze: the maze
    @param start: the start
    @param destination: the destination
    @return: the shortest distance for the ball to stop at the destination
    """
    def shortestDistance(self, maze, start, destination):
        start, destination = tuple(start), tuple(destination)
        row,col = len(maze),len(maze[0])
        def neighbors(maze, node):
            temp = []
            used = set()
            used.add(node)
            for dx, dy in [(-1, 0), (0, 1), (0, -1), (1, 0)]:
                (x,y), dist = node, 0
                while 0 <= x+dx < row and 0 <= y+dy < col and maze[x+dx][y+dy] == 0:
                    x += dx
                    y += dy
                    dist += 1
                if (x,y) not in used:
                    temp.append((dist, (x,y)))
            return temp

        heap = [(0, start)]
        visited = set()
        while heap:
            dist, node = heapq.heappop(heap)
            if node in visited: continue
            if node == destination:
                return dist
            visited.add(node)
            for neighbor_dist, neighbor in neighbors(maze, node):
                heapq.heappush(heap, (dist+neighbor_dist, neighbor))
        return -1

heap 을 이용한건데... 하...

<예시>

0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0

1. start 부터 heap 시작

2. visited 로 지나간 곳 표시

3. neighbors(maze, node)
   => 막다른 길을 만날 때까지 사방으로 직진해서 (거리, 좌표) 를 temp 리스트에 넣어주기
   => 사방(이웃)의 끝들을 알려줌
   ex) neighbors(maze, (0, 4)) = [(1, (0, 3)), (2, (2, 4))]

4. 이웃과 합친 거리 dist 와 이웃 노드 값을 heap 에 넣어주기

사방 확인하는 코드

for dx, dy in [(-1, 0), (0, 1), (0, -1), (1, 0)]:
	if 0 <= x+dx < row and 0 <= y+dy < col:

조건문으로 확인하면 넘 길어지는데 이렇게 하면 간단함
알아두자...!!!

---

1000. Minimum Cost to Merge Stones

There are n piles of stones arranged in a row. The ith pile has stones[i] stones.

A move consists of merging exactly k consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these k piles.

Return the minimum cost to merge all piles of stones into one pile. If it is impossible, return -1.

(다시보기)