|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|5 초||128 MB||15||8||5||50.000%|
You have an n×n game board. Some squares contain obstacles, except the left- and right-most columns which are obstacle-free. The left-most column is filled with your n pieces, 1 per row. Your goal is to move all your pieces to the right-most column as quickly as possible. In a given turn, you can move each piece N, S, E, or W one space, or leave that piece in place. A piece cannot move onto a square containing an obstacle, nor may two pieces move to the same square on the same turn. All pieces move simultaneously, so one may move to a location currently occupied by another piece so long as that piece itself moves elsewhere at the same time.
Given n and the obstacles, determine the fewest number of turns needed to get all your pieces to the right-hand side of the board.
Each test case starts with a positive integer n indicating the size of the game board, with n ≤ 25. Following this will be n lines containing n characters each. If the jth character in the ith line is an ‘X’, then there is an obstacle in board location i, j; otherwise this character will be a ‘.’ indicating no obstacle. There will never be an obstacle in the 0th or (n−1)st column and there will always be at least one obstacle-free path between these two columns. A line containing a single 0 will terminate input.
For each test case output the minimum number of turns to move all the pieces from the left side of the board to the right side.
5 ..... .X... ...X. ..X.. ..... 5 .X... .X... .X... .XXX. ..... 0
Case 1: 6 Case 2: 8