크기가 100 이하인 격자에 2x2 상자 하나와 2x2 보관 위치 하나를 배치해 풀이에 40000회 이상의 이동이 필요한 Bigger Sokoban 퍼즐을 설계한다.
어려움9시뮬레이션구현완전 탐색그리디아직 제출이 없습니다시간 제한1초메모리 제한1024 MBSokoban is a famous puzzle game, where the player moves around in the N×M-size grid, and pushes 1×1-size boxes to 1×1-size storage locations.
Bigger Sokoban is a possible variation of Sokoban, but the size of boxes and storage locations are bigger than 1×1. This problem especially uses 2×2 for both.
The rule of Bigger Sokoban is the same as Sokoban. Each square in the grid is an empty square or a wall. Some 2×2 area of empty squares contain 2×2-size box each and some 2×2 area of empty squares are marked as 2×2-size storage location each.
The player is in the grid and may move up, down, left, right to the adjacent empty squares, but should not go through walls, boxes, or outside of the grid. If the player tries to move into a box, it is pushed to the adjacent squares in that direction. Boxes must not be pushed to other boxes, walls, or outside of the grid, and they cannot be pulled. The number of boxes is equal to the number of storage locations. The puzzle is solved when all boxes are at the storage locations.
Your mission is to make a Bigger Sokoban grid that needs at least 40 000 moves to solve. To make the situation easier, the grid must satisfy the following constraints:
There are no inputs for this problem.
In the first line, print two space-separated integers N, M; they describe the size of the grid.
In each of the following N lines, print a string of length M; it describes each row of the grid. Each string must consist of ., #, P, B, S; each character means empty square, wall, player, box, storage location respectively.
The grid must contain exactly one P, exactly four B, and exactly four S. B and S each must form a 2×2 square. The grid, of course, must be solvable.
Note that the sample output is only to demonstrate a well-formatted output. Since it can be solved in less than 40 000 moves, it is not a correct answer.