<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

472. Sokoban
Time limit per test: 0.75 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Sokoban (warehouse keeper) is a transport puzzle in which the player pushes boxes around a maze, viewed from above, and tries to put them in designated locations. Only one box may be pushed at a time, and boxes cannot be pulled. The problem of solving Sokoban puzzles has been proven to be NP-hard.

From Wikipedia, the free encyclopedia

Probably, everybody at least once in his life played this famous game. And despite the fact the problem is NP-hard you are required to write a program which solves this puzzle for quite huge mazes; moreover, it is needed to find the best solution to the puzzle. Specifically, from all possible solutions you are to select the one with the smallest number of box pushes. From all such solutions you need the one that minimizes the total number of moves. To simplify your task a bit, only puzzles with one box will be given to your program to solve.

Input
Maze for solving is given in the input file, maze has a size up to 100 x 100 cells. Every line of input file represents one row of the maze, all lines have the same length (and equal to the width of the maze). Space character represents a passable cell, where box and sokoban may stay, and "#" character represents an impassable wall. "@" character represents sokoban itself, ""representsacellinwhichtheboxisinitiallylocated, and"."representsacellwheresokobanshouldputthebox.Cellsinwhichsokoban, boxanddestinationcellareinitiallylocatedarepassable.Inputfilewillcontaineveryofthecharacters"@", "" and "." exactly once. Maze will be closed in a sense that sokoban will be unable to leave it.

Output
If there is no solution for the given maze, write to the output file the only message "Impossible.". Otherwise write one of the best (in the abovementioned sense) solutions. Each move is represented by one of the four characters: "u" means moving up, "r" — right, "d" — down and "l" — left. Use capital letters (i.e. "U", "R", "D" and "L") to represent moves when sokoban pushes the box.

Example(s)
ddrruuLulD
sample input
sample output
#### 
#  ##
#@ # #.# # #   # #####

sampleinput
sampleoutput
####
#  ##
#@ #
#.# #
# # #
#####
Impossible.

<|response|>
## 1. Abridged problem statement

Given a rectangular Sokoban maze with:

- walls `#`,
- empty/passable cells `' '`,
- one player `@`,
- one box `$`,
- one target `.`,

find a sequence of moves that puts the box on the target.

The solution must be optimal by:

1. minimum number of box pushes,
2. among those, minimum total number of player moves.

Output moves as:

- lowercase `u`, `d`, `l`, `r` for ordinary walking,
- uppercase `U`, `D`, `L`, `R` for pushes.

If no solution exists, output:

```text
Impossible.
```

---

## 2. Key observations needed to solve the problem

### Observation 1: There is only one box

A full Sokoban state would normally include positions of all boxes and the player. Here there is only one box, so we only need to track:

```text
box position
player position
```

However, we can compress this even further.

---

### Observation 2: After every push, the player is next to the box

Suppose the box is pushed upward.

Before the push:

```text
player
box
```

After the push:

```text
box
player
```

So after any push, the player is standing on the old box cell, adjacent to the new box position.

Therefore, after a push, it is enough to know:

```text
(box position, side of box where player stands)
```

There are only:

```text
rows * cols * 4
```

such states.

---

### Observation 3: Walking between pushes can be handled by BFS

From a state, to push the box in some direction `d`:

- the cell in front of the box must be passable,
- the player must be able to walk to the cell behind the box,
- during that walk, the current box cell is treated as blocked.

This reachability and shortest walking distance can be found by BFS on the grid.

---

### Observation 4: The cost is lexicographic

We minimize:

```text
(number of pushes, total moves)
```

A walking move costs:

```text
(+0 pushes, +1 move)
```

A push costs:

```text
(+1 push, +1 move)
```

So each transition between compressed states has cost:

```text
(+1 push, walking_distance + 1 moves)
```

We can run Dijkstra with distance pairs:

```text
(pushes, moves)
```

compared lexicographically.

---

## 3. Full solution approach based on the observations

### State definition

Let a state be:

```text
(box_cell, side)
```

where `side` tells where the player stands relative to the box.

For example, if `side = up`, then the player is at the cell above the box.

We encode:

```text
state = box_cell * 4 + side
```

---

### Transitions

From state `(box, side)`:

1. Recover the current player position from the box position and side.
2. Run BFS from the player position, treating the current box cell as blocked.
3. For every direction `d`:
   - the player must reach the cell behind the box,
   - the cell in front of the box must be passable.
4. If valid, push the box one cell in direction `d`.

The successor state becomes:

```text
(new_box_position, opposite(d))
```

because after the push, the player stands on the old box cell, which is behind the new box.

The cost added is:

```text
+1 push
+walking_distance_to_push_position + 1 moves
```

---

### Initial states

Initially, the player may be anywhere, not necessarily adjacent to the box.

So we do one BFS from the initial player position with the initial box cell blocked. Then we generate all first possible pushes.

---

### Goal

The first time Dijkstra pops a state whose box position is the target, that state is optimal.

This is true because Dijkstra processes states in increasing order of:

```text
(pushes, moves)
```

---

### Reconstructing the answer

For each relaxed state, store:

```text
parent state
push direction used to enter this state
```

After reaching the target:

1. Follow parent pointers backward.
2. Reverse the chain.
3. For each push:
   - recompute a shortest walking path to the required pushing cell,
   - append lowercase walking moves,
   - append uppercase push move.

---

### Complexity

Let:

```text
N = rows * cols
```

There are at most:

```text
4N
```

compressed states.

For each processed state, we may run one BFS over the maze:

```text
O(N)
```

So the worst-case complexity is approximately:

```text
O(4N * N log N)
```

For `100 x 100` mazes and one box, this is acceptable.

Memory usage is:

```text
O(N)
```

for BFS arrays plus:

```text
O(4N)
```

for Dijkstra arrays.

---

## 4. C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

// Directions: up, down, left, right.
const int DR[4] = {-1, 1, 0, 0};
const int DC[4] = {0, 0, -1, 1};

// Opposite direction.
const int OPP[4] = {1, 0, 3, 2};

// Output characters.
const char LOW[4] = {'u', 'd', 'l', 'r'};
const char UPP[4] = {'U', 'D', 'L', 'R'};

int rows, cols;
vector<string> grid;

int startPlayer, startBox, targetCell;

void readInput() {
    vector<string> raw;
    string line;

    // Read whole input. getline preserves spaces inside each row.
    while (getline(cin, line)) {
        if (!line.empty() && line.back() == '\r') {
            line.pop_back();
        }
        raw.push_back(line);
    }

    rows = (int)raw.size();
    cols = 0;

    for (const string& s : raw) {
        cols = max(cols, (int)s.size());
    }

    // Pad with walls for safety.
    grid.assign(rows, string(cols, '#'));

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < (int)raw[r].size(); c++) {
            grid[r][c] = raw[r][c];
        }
    }

    startPlayer = startBox = targetCell = -1;

    // Locate special cells and replace them with passable cells.
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == '@') {
                startPlayer = r * cols + c;
                grid[r][c] = ' ';
            } else if (grid[r][c] == '$') {
                startBox = r * cols + c;
                grid[r][c] = ' ';
            } else if (grid[r][c] == '.') {
                targetCell = r * cols + c;
                grid[r][c] = ' ';
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    readInput();

    if (rows == 0) {
        return 0;
    }

    int cells = rows * cols;
    int states = cells * 4;

    // If already solved.
    if (startBox == targetCell) {
        cout << '\n';
        return 0;
    }

    // Reusable BFS data for computing walking distances.
    vector<int> walkDist(cells, 0);
    vector<int> walkSeen(cells, 0);
    vector<int> bfsQueue(cells);
    int walkTimer = 0;

    auto inside = [&](int r, int c) {
        return r >= 0 && r < rows && c >= 0 && c < cols;
    };

    auto passable = [&](int r, int c) {
        return inside(r, c) && grid[r][c] != '#';
    };

    /*
        BFS from src while treating obstacle as blocked.

        It fills:
        - walkSeen[cell] == walkTimer if cell is reachable,
        - walkDist[cell] = shortest walking distance.
    */
    auto bfsDistance = [&](int src, int obstacle) {
        walkTimer++;

        int head = 0, tail = 0;
        walkSeen[src] = walkTimer;
        walkDist[src] = 0;
        bfsQueue[tail++] = src;

        while (head < tail) {
            int cur = bfsQueue[head++];

            int r = cur / cols;
            int c = cur % cols;

            for (int d = 0; d < 4; d++) {
                int nr = r + DR[d];
                int nc = c + DC[d];

                if (!inside(nr, nc)) {
                    continue;
                }

                int nxt = nr * cols + nc;

                if (grid[nr][nc] == '#' || nxt == obstacle) {
                    continue;
                }

                if (walkSeen[nxt] == walkTimer) {
                    continue;
                }

                walkSeen[nxt] = walkTimer;
                walkDist[nxt] = walkDist[cur] + 1;
                bfsQueue[tail++] = nxt;
            }
        }
    };

    const long long INF = (long long)4e18;

    vector<int> distPush(states, INT_MAX);
    vector<long long> distMove(states, INF);

    // Parent information for reconstruction.
    vector<int> parent(states, -2);
    vector<int> parentDir(states, -1);

    using Node = tuple<int, long long, int>;
    priority_queue<Node, vector<Node>, greater<Node>> pq;

    auto relax = [&](int st, int pushes, long long moves, int from, int dir) {
        if (
            pushes < distPush[st] ||
            (pushes == distPush[st] && moves < distMove[st])
        ) {
            distPush[st] = pushes;
            distMove[st] = moves;
            parent[st] = from;
            parentDir[st] = dir;
            pq.push({pushes, moves, st});
        }
    };

    /*
        Try all pushes from the current configuration.

        box: current box cell
        player: current player cell
        fromState: compressed predecessor state
        basePushes/baseMoves: current Dijkstra cost
    */
    auto tryPushes = [&](int box, int player, int fromState,
                         int basePushes, long long baseMoves) {
        bfsDistance(player, box);

        int br = box / cols;
        int bc = box % cols;

        for (int d = 0; d < 4; d++) {
            // Cell where player must stand before pushing.
            int behindR = br - DR[d];
            int behindC = bc - DC[d];

            // Cell where box will move.
            int frontR = br + DR[d];
            int frontC = bc + DC[d];

            if (!passable(behindR, behindC)) {
                continue;
            }

            if (!passable(frontR, frontC)) {
                continue;
            }

            int behind = behindR * cols + behindC;

            // Player must be able to walk to the pushing position.
            if (walkSeen[behind] != walkTimer) {
                continue;
            }

            int newBox = frontR * cols + frontC;

            // After pushing in direction d, player is opposite d from new box.
            int newState = newBox * 4 + OPP[d];

            relax(
                newState,
                basePushes + 1,
                baseMoves + walkDist[behind] + 1,
                fromState,
                d
            );
        }
    };

    // Generate initial pushes.
    tryPushes(startBox, startPlayer, -1, 0, 0);

    int goalState = -1;

    // Dijkstra over compressed states.
    while (!pq.empty()) {
        auto [pushes, moves, st] = pq.top();
        pq.pop();

        if (pushes != distPush[st] || moves != distMove[st]) {
            continue;
        }

        int box = st / 4;
        int side = st % 4;

        if (box == targetCell) {
            goalState = st;
            break;
        }

        int br = box / cols;
        int bc = box % cols;

        // Recover player position from side.
        int playerR = br + DR[side];
        int playerC = bc + DC[side];
        int player = playerR * cols + playerC;

        tryPushes(box, player, st, pushes, moves);
    }

    if (goalState == -1) {
        cout << "Impossible.\n";
        return 0;
    }

    // Recover chain of states, each state corresponding to one performed push.
    vector<int> chain;
    for (int cur = goalState; cur != -1; cur = parent[cur]) {
        chain.push_back(cur);
    }
    reverse(chain.begin(), chain.end());

    // BFS arrays for reconstructing actual walking paths.
    vector<int> pathSeen(cells, 0);
    vector<int> pathParent(cells, -1);
    vector<int> pathParentDir(cells, -1);
    int pathTimer = 0;

    /*
        Return one shortest lowercase walking path from src to dst,
        avoiding obstacle.
    */
    auto bfsPath = [&](int src, int dst, int obstacle) {
        string result;

        if (src == dst) {
            return result;
        }

        pathTimer++;

        int head = 0, tail = 0;
        pathSeen[src] = pathTimer;
        pathParent[src] = -1;
        bfsQueue[tail++] = src;

        while (head < tail) {
            int cur = bfsQueue[head++];

            if (cur == dst) {
                break;
            }

            int r = cur / cols;
            int c = cur % cols;

            for (int d = 0; d < 4; d++) {
                int nr = r + DR[d];
                int nc = c + DC[d];

                if (!inside(nr, nc)) {
                    continue;
                }

                int nxt = nr * cols + nc;

                if (grid[nr][nc] == '#' || nxt == obstacle) {
                    continue;
                }

                if (pathSeen[nxt] == pathTimer) {
                    continue;
                }

                pathSeen[nxt] = pathTimer;
                pathParent[nxt] = cur;
                pathParentDir[nxt] = d;
                bfsQueue[tail++] = nxt;
            }
        }

        // Reconstruct path backwards.
        for (int cur = dst; cur != src; cur = pathParent[cur]) {
            int d = pathParentDir[cur];
            result.push_back(LOW[d]);
        }

        reverse(result.begin(), result.end());
        return result;
    };

    string answer;

    for (int st : chain) {
        int pushDir = parentDir[st];
        int prevState = parent[st];

        int prevBox;
        int prevPlayer;

        if (prevState == -1) {
            prevBox = startBox;
            prevPlayer = startPlayer;
        } else {
            prevBox = prevState / 4;
            int prevSide = prevState % 4;

            int br = prevBox / cols;
            int bc = prevBox % cols;

            prevPlayer = (br + DR[prevSide]) * cols + (bc + DC[prevSide]);
        }

        int br = prevBox / cols;
        int bc = prevBox % cols;

        // Cell where player must stand before this push.
        int behind = (br - DR[pushDir]) * cols + (bc - DC[pushDir]);

        answer += bfsPath(prevPlayer, behind, prevBox);
        answer.push_back(UPP[pushDir]);
    }

    cout << answer << '\n';

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys
import heapq


# Directions: up, down, left, right.
DR = [-1, 1, 0, 0]
DC = [0, 0, -1, 1]

# Opposite directions.
OPP = [1, 0, 3, 2]

# Output characters.
LOW = ['u', 'd', 'l', 'r']
UPP = ['U', 'D', 'L', 'R']


def solve():
    raw = sys.stdin.read().splitlines()

    if not raw:
        return

    rows = len(raw)
    cols = max(len(line) for line in raw)

    # Pad with walls for safety.
    grid = [['#'] * cols for _ in range(rows)]

    for r, line in enumerate(raw):
        for c, ch in enumerate(line):
            grid[r][c] = ch

    start_player = -1
    start_box = -1
    target = -1

    # Locate special cells.
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '@':
                start_player = r * cols + c
                grid[r][c] = ' '
            elif grid[r][c] == '$':
                start_box = r * cols + c
                grid[r][c] = ' '
            elif grid[r][c] == '.':
                target = r * cols + c
                grid[r][c] = ' '

    cells = rows * cols
    states = cells * 4

    if start_box == target:
        print()
        return

    def inside(r, c):
        return 0 <= r < rows and 0 <= c < cols

    def passable(r, c):
        return inside(r, c) and grid[r][c] != '#'

    # Reusable BFS arrays for walking distance.
    walk_dist = [0] * cells
    walk_seen = [0] * cells
    walk_timer = 0

    bfs_queue = [0] * cells

    def bfs_distance(src, obstacle):
        """
        BFS from src while treating obstacle as blocked.

        After this:
        walk_seen[cell] == walk_timer means reachable,
        walk_dist[cell] is the shortest walking distance.
        """
        nonlocal walk_timer

        walk_timer += 1

        head = 0
        tail = 0

        walk_seen[src] = walk_timer
        walk_dist[src] = 0
        bfs_queue[tail] = src
        tail += 1

        while head < tail:
            cur = bfs_queue[head]
            head += 1

            r = cur // cols
            c = cur % cols

            for d in range(4):
                nr = r + DR[d]
                nc = c + DC[d]

                if not inside(nr, nc):
                    continue

                nxt = nr * cols + nc

                if grid[nr][nc] == '#' or nxt == obstacle:
                    continue

                if walk_seen[nxt] == walk_timer:
                    continue

                walk_seen[nxt] = walk_timer
                walk_dist[nxt] = walk_dist[cur] + 1

                bfs_queue[tail] = nxt
                tail += 1

    INF = 10**30

    dist_push = [10**9] * states
    dist_move = [INF] * states

    parent = [-2] * states
    parent_dir = [-1] * states

    pq = []

    def relax(st, pushes, moves, from_state, push_dir):
        """
        Relax Dijkstra state.
        Distances are compared lexicographically:
        first pushes, then moves.
        """
        if (
            pushes < dist_push[st]
            or (pushes == dist_push[st] and moves < dist_move[st])
        ):
            dist_push[st] = pushes
            dist_move[st] = moves
            parent[st] = from_state
            parent_dir[st] = push_dir
            heapq.heappush(pq, (pushes, moves, st))

    def try_pushes(box, player, from_state, base_pushes, base_moves):
        """
        Try all possible pushes from current configuration.
        """
        bfs_distance(player, box)

        br = box // cols
        bc = box % cols

        for d in range(4):
            # Player must stand behind the box.
            behind_r = br - DR[d]
            behind_c = bc - DC[d]

            # Box moves into the front cell.
            front_r = br + DR[d]
            front_c = bc + DC[d]

            if not passable(behind_r, behind_c):
                continue

            if not passable(front_r, front_c):
                continue

            behind = behind_r * cols + behind_c

            # Player must be able to reach the pushing position.
            if walk_seen[behind] != walk_timer:
                continue

            new_box = front_r * cols + front_c

            # After push, player is opposite direction from the new box.
            new_state = new_box * 4 + OPP[d]

            relax(
                new_state,
                base_pushes + 1,
                base_moves + walk_dist[behind] + 1,
                from_state,
                d,
            )

    # Generate first pushes from initial position.
    try_pushes(start_box, start_player, -1, 0, 0)

    goal_state = -1

    # Dijkstra search.
    while pq:
        pushes, moves, st = heapq.heappop(pq)

        if pushes != dist_push[st] or moves != dist_move[st]:
            continue

        box = st // 4
        side = st % 4

        if box == target:
            goal_state = st
            break

        br = box // cols
        bc = box % cols

        # Recover player position from side.
        player_r = br + DR[side]
        player_c = bc + DC[side]
        player = player_r * cols + player_c

        try_pushes(box, player, st, pushes, moves)

    if goal_state == -1:
        print("Impossible.")
        return

    # Recover chain of pushed states.
    chain = []
    cur = goal_state

    while cur != -1:
        chain.append(cur)
        cur = parent[cur]

    chain.reverse()

    # BFS arrays for reconstructing walking paths.
    path_seen = [0] * cells
    path_parent = [-1] * cells
    path_parent_dir = [-1] * cells
    path_timer = 0

    def bfs_path(src, dst, obstacle):
        """
        Return one shortest lowercase walking path from src to dst,
        avoiding obstacle.
        """
        nonlocal path_timer

        if src == dst:
            return ""

        path_timer += 1

        head = 0
        tail = 0

        path_seen[src] = path_timer
        path_parent[src] = -1
        bfs_queue[tail] = src
        tail += 1

        while head < tail:
            cur = bfs_queue[head]
            head += 1

            if cur == dst:
                break

            r = cur // cols
            c = cur % cols

            for d in range(4):
                nr = r + DR[d]
                nc = c + DC[d]

                if not inside(nr, nc):
                    continue

                nxt = nr * cols + nc

                if grid[nr][nc] == '#' or nxt == obstacle:
                    continue

                if path_seen[nxt] == path_timer:
                    continue

                path_seen[nxt] = path_timer
                path_parent[nxt] = cur
                path_parent_dir[nxt] = d

                bfs_queue[tail] = nxt
                tail += 1

        # Reconstruct path backwards.
        result = []
        cur = dst

        while cur != src:
            d = path_parent_dir[cur]
            result.append(LOW[d])
            cur = path_parent[cur]

        result.reverse()
        return ''.join(result)

    answer = []

    for st in chain:
        push_dir = parent_dir[st]
        prev_state = parent[st]

        if prev_state == -1:
            prev_box = start_box
            prev_player = start_player
        else:
            prev_box = prev_state // 4
            prev_side = prev_state % 4

            br = prev_box // cols
            bc = prev_box % cols

            prev_player = (br + DR[prev_side]) * cols + (bc + DC[prev_side])

        br = prev_box // cols
        bc = prev_box % cols

        # Required cell for player before pushing.
        behind = (br - DR[push_dir]) * cols + (bc - DC[push_dir])

        answer.append(bfs_path(prev_player, behind, prev_box))
        answer.append(UPP[push_dir])

    print(''.join(answer))


if __name__ == "__main__":
    solve()
```