소코반

시간 제한10초메모리 제한1024 MB

요약

최대 4개의 상자가 있는 소코반 격자에서 모든 상자를 보관 위치로 옮기는 데 필요한 최소 상자 밀기 횟수를 구합니다.

난이도: 보통10점 중 6점
유형: 최단 경로, BFS, 그래프
정답자: 아직 제출이 없습니다

문제

소코반은 퍼즐 비디오 게임이다. 과제는 주어진 퍼즐을 풀기 위해 필요한 상자 밀기 횟수의 최솟값을 구하는 것이다. 플레이어가 움직인 횟수는 중요하지 않다.

게임은 격자 위에서 진행된다. 매 단계마다 플레이어는 상하좌우로 인접한 칸 중 하나로 이동할 수 있다. 일부 칸은 벽이고, 일부 칸에는 상자가 놓여 있다. 특정 칸은 보관 위치로 지정되어 있으며, 플레이어는 모든 상자를 이 보관 위치 중 하나로 밀어야 한다. 플레이어는 상자가 있는 칸으로 들어가 상자를 그 너머 칸으로 밀어낸다. 상자 너머 칸이 비어 있어야 상자를 밀 수 있다. 상자를 다른 상자나 벽 안으로 밀 수 없다. 상자는 당기거나 다른 방식으로 옮길 수 없으며, 오직 밀어서만 옮길 수 있다. 이미 보관 위치에 있는 상자도 여전히 밀 수 있다. 마지막에 모든 상자가 보관 위치에 놓여 있어야 한다.

입력

격자의 크기는 $N \times M$ 이며, $N$ 개의 줄로 주어진다. 각 줄은 최대 $M$ 개의 문자로 이루어지고, 줄 끝에 공백이 없어서 일부 줄은 $M$ 보다 짧을 수 있다. 플레이어는 벽으로 둘러싸인 영역 안에 있다. 상자 수 $B$ 는 보관 위치 수와 같다. 각 문자의 의미는 다음과 같다.

'#' - 벽
' ' - 빈 칸
'.' - 빈 보관 위치
'@' - 보관 위치가 아닌 칸에 서 있는 플레이어
'+' - 보관 위치에 서 있는 플레이어
'$' - 보관 위치가 아닌 칸에 놓인 상자
'*' - 보관 위치에 놓인 상자

출력

퍼즐을 풀기 위해 필요한 상자 밀기 횟수의 최솟값을 한 줄에 출력한다. 주어진 퍼즐은 풀 수 있다고 보장된다.

제한

$3 \leq N, M \leq 8$
$1 \leq B \leq 4$

예제3

예제 1

입력

###
#.#####
#..   #
# $$$@#
#    ##
######

예상 출력

예제 2

입력

####
#. ####
#.$   #
#@ $$ #
###.  #
  #####

예상 출력

예제 3

입력

 ####
 #  #
##  ###
#.  $ #
# +$* #
#     #
#######

예상 출력