<|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, "$" represents a cell in which the box is initially located, and "." represents a cell where sokoban should put the box. Cells in which sokoban, box and destination cell are initially located are passable. Input file will contain every of the characters "@", "$" 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 comments

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const int dr[4] = {-1, 1, 0, 0};
const int dc[4] = {0, 0, -1, 1};
const int opp[4] = {1, 0, 3, 2};
const char low[4] = {'u', 'd', 'l', 'r'};
const char upp[4] = {'U', 'D', 'L', 'R'};

int rows, cols;
vector<string> grid;
int start_keeper, start_box, target;

void read() {
    vector<string> raw;
    string line;
    while(getline(cin, line)) {
        if(!line.empty() && line.back() == '\r') {
            line.pop_back();
        }
        raw.push_back(line);
    }

    rows = raw.size();
    cols = 0;
    for(auto& s: raw) {
        cols = max(cols, (int)s.size());
    }

    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];
        }
    }

    start_keeper = start_box = target = -1;
    for(int r = 0; r < rows; r++) {
        for(int c = 0; c < cols; c++) {
            if(grid[r][c] == '@') {
                start_keeper = r * cols + c;
                grid[r][c] = ' ';
            } else if(grid[r][c] == '$') {
                start_box = r * cols + c;
                grid[r][c] = ' ';
            } else if(grid[r][c] == '.') {
                target = r * cols + c;
                grid[r][c] = ' ';
            }
        }
    }
}

void solve() {
    // We search over states (box cell, side), where "side" records which of
    // the four cells neighbouring the box the keeper stands on, i.e. the cell
    // the box was last pushed from. A push in direction d is possible only when
    // the keeper can walk to the cell directly behind the box (opposite to d)
    // and the cell in front of the box is free; the push then advances the box
    // one cell and moves the keeper onto the box's old cell.
    //
    // The objective is lexicographic: first minimise the number of pushes, then
    // the total number of keeper moves. This is a shortest path with cost
    // (pushes, moves) compared lexicographically, so we run Dijkstra over the
    // (box, side) states. Walking the keeper does between two consecutive
    // pushes costs no push and contributes its length in moves; for a popped
    // state we recover those lengths with a single grid BFS from the keeper's
    // cell that treats the box as a wall, yielding the distance to every
    // reachable push position at once.
    //
    // Pushing in direction d from box cell B sends the box to B + d and the
    // keeper to B, so the successor is (B + d, opposite(d)) with one extra push
    // and (walk distance to B - d) + 1 extra moves. The keeper's starting cell
    // is handled by one initial BFS that seeds every possible first push. The
    // first popped state whose box sits on the target cell is optimal.
    //
    // To print a solution we follow the predecessor chain and, for each
    // recorded push, recompute the keeper's walking path with a BFS that tracks
    // parents, emitting lower case letters for plain moves and the upper case
    // letter for the push itself. If no state with the box on the target is
    // ever popped the puzzle is unsolvable.

    if(start_box == target) {
        cout << "\n";
        return;
    }

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

    vector<int> walk_dist(cells), walk_seen(cells, 0);
    vector<int> bfs_queue(cells);
    int walk_timer = 0;

    auto bfs_dist = [&](int src, int obstacle) {
        walk_timer++;
        int orow = obstacle / cols, ocol = obstacle % cols;
        int need = 0;
        for(int k = 0; k < 4; k++) {
            int nr = orow + dr[k], nc = ocol + dc[k];
            if(nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
               grid[nr][nc] != '#') {
                need++;
            }
        }

        int found = 0, head = 0, tail = 0;
        walk_seen[src] = walk_timer;
        walk_dist[src] = 0;
        bfs_queue[tail++] = src;
        if(abs(src / cols - orow) + abs(src % cols - ocol) == 1) {
            found++;
        }

        while(head < tail && found < need) {
            int cur = bfs_queue[head++];
            int cr = cur / cols, cc = cur % cols, cd = walk_dist[cur];
            for(int k = 0; k < 4; k++) {
                int nr = cr + dr[k], nc = cc + dc[k];
                if(nr < 0 || nr >= rows || nc < 0 || nc >= cols) {
                    continue;
                }
                int ncell = nr * cols + nc;
                if(grid[nr][nc] == '#' || ncell == obstacle) {
                    continue;
                }
                if(walk_seen[ncell] == walk_timer) {
                    continue;
                }

                walk_seen[ncell] = walk_timer;
                walk_dist[ncell] = cd + 1;
                bfs_queue[tail++] = ncell;
                if(abs(nr - orow) + abs(nc - ocol) == 1) {
                    found++;
                }
            }
        }
    };

    const int INF = INT_MAX;
    vector<int> dist_push(states, INF), dist_move(states, INF);
    vector<int> par(states, -2), par_dir(states, -1);

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

    auto relax = [&](int st, int np, int nm, int from, int dir) {
        if(np < dist_push[st] || (np == dist_push[st] && nm < dist_move[st])) {
            dist_push[st] = np;
            dist_move[st] = nm;
            par[st] = from;
            par_dir[st] = dir;
            pq.push({np, nm, st});
        }
    };

    auto try_pushes = [&](int box, int keeper, int from, int base_push,
                          int base_move) {
        bfs_dist(keeper, box);
        int brow = box / cols, bcol = box % cols;
        for(int i = 0; i < 4; i++) {
            int wr = brow - dr[i], wc = bcol - dc[i];
            int fr = brow + dr[i], fc = bcol + dc[i];
            if(wr < 0 || wr >= rows || wc < 0 || wc >= cols) {
                continue;
            }
            if(fr < 0 || fr >= rows || fc < 0 || fc >= cols) {
                continue;
            }
            if(grid[wr][wc] == '#' || grid[fr][fc] == '#') {
                continue;
            }

            int behind = wr * cols + wc;
            if(walk_seen[behind] != walk_timer) {
                continue;
            }

            int new_box = fr * cols + fc;
            int new_state = new_box * 4 + opp[i];
            relax(
                new_state, base_push + 1, base_move + walk_dist[behind] + 1,
                from, i
            );
        }
    };

    try_pushes(start_box, start_keeper, -1, 0, 0);

    int goal_state = -1;
    while(!pq.empty()) {
        auto [pp, mm, st] = pq.top();
        pq.pop();
        if(pp != dist_push[st] || mm != dist_move[st]) {
            continue;
        }

        int box = st / 4, side = st % 4;
        if(box == target) {
            goal_state = st;
            break;
        }

        int keeper = (box / cols + dr[side]) * cols + (box % cols + dc[side]);
        try_pushes(box, keeper, st, pp, mm);
    }

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

    vector<int> chain;
    for(int cur = goal_state; cur != -1; cur = par[cur]) {
        chain.push_back(cur);
    }
    reverse(chain.begin(), chain.end());

    vector<int> path_seen(cells, 0), path_par(cells), path_par_dir(cells);
    int path_timer = 0;

    auto bfs_path = [&](int src, int dst, int obstacle) {
        string moves;
        if(src == dst) {
            return moves;
        }

        path_timer++;
        int head = 0, tail = 0;
        path_seen[src] = path_timer;
        path_par[src] = -1;
        bfs_queue[tail++] = src;

        while(head < tail) {
            int cur = bfs_queue[head++];
            if(cur == dst) {
                break;
            }

            int cr = cur / cols, cc = cur % cols;
            for(int k = 0; k < 4; k++) {
                int nr = cr + dr[k], nc = cc + dc[k];
                if(nr < 0 || nr >= rows || nc < 0 || nc >= cols) {
                    continue;
                }
                int ncell = nr * cols + nc;
                if(grid[nr][nc] == '#' || ncell == obstacle) {
                    continue;
                }
                if(path_seen[ncell] == path_timer) {
                    continue;
                }

                path_seen[ncell] = path_timer;
                path_par[ncell] = cur;
                path_par_dir[ncell] = k;
                bfs_queue[tail++] = ncell;
            }
        }

        for(int cur = dst; cur != src; cur = path_par[cur]) {
            moves += low[path_par_dir[cur]];
        }
        reverse(moves.begin(), moves.end());
        return moves;
    };

    string result;
    for(int st: chain) {
        int dir = par_dir[st];
        int prev = par[st];

        int prev_box, prev_keeper;
        if(prev == -1) {
            prev_box = start_box;
            prev_keeper = start_keeper;
        } else {
            int pb = prev / 4, ps = prev % 4;
            prev_box = pb;
            prev_keeper = (pb / cols + dr[ps]) * cols + (pb % cols + dc[ps]);
        }

        int behind =
            (prev_box / cols - dr[dir]) * cols + (prev_box % cols - dc[dir]);
        result += bfs_path(prev_keeper, behind, prev_box);
        result += upp[dir];
    }

    cout << result << "\n";
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 5. Python implementation with comments

```python
import sys
import heapq
from collections import deque


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

# Opposite direction for each direction.
OPP = [1, 0, 3, 2]

# Lowercase letters for ordinary moves.
LOW = ['u', 'd', 'l', 'r']

# Uppercase letters for pushes.
UPP = ['U', 'D', 'L', 'R']


def solve():
    # Read all input lines without removing spaces.
    raw = sys.stdin.read().splitlines()

    # If input is empty, do nothing.
    if not raw:
        return

    # Remove possible Windows carriage returns.
    raw = [line.rstrip('\r') for line in raw]

    # Number of rows.
    rows = len(raw)

    # Normalize width.
    cols = max(len(line) for line in raw)

    # Create rectangular grid padded with walls.
    grid = [['#'] * cols for _ in range(rows)]

    # Copy input characters into the rectangular grid.
    for r in range(rows):
        for c, ch in enumerate(raw[r]):
            grid[r][c] = ch

    # Special positions.
    start_keeper = -1
    start_box = -1
    target = -1

    # Find @, $, and ., then replace them by empty cells.
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '@':
                start_keeper = 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] = ' '

    # If box is already on target, no moves are needed.
    if start_box == target:
        print()
        return

    # Total number of cells.
    cells = rows * cols

    # Total number of compressed states.
    states = cells * 4

    # Arrays used for walking BFS.
    walk_dist = [0] * cells
    walk_seen = [0] * cells
    walk_timer = 0

    # Reusable queue array for BFS.
    bfs_queue = [0] * cells

    def bfs_dist(src, obstacle):
        nonlocal walk_timer
        walk_timer += 1
        orow = obstacle // cols
        ocol = obstacle % cols
        need = 0
        for k in range(4):
            nr = orow + DR[k]
            nc = ocol + DC[k]
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != '#':
                need += 1
        found = 0
        head = 0
        tail = 0
        walk_seen[src] = walk_timer
        walk_dist[src] = 0
        bfs_queue[tail] = src
        tail += 1
        if abs(src // cols - orow) + abs(src % cols - ocol) == 1:
            found += 1
        while head < tail and found < need:
            cur = bfs_queue[head]
            head += 1
            cr = cur // cols
            cc = cur % cols
            cd = walk_dist[cur]
            for k in range(4):
                nr = cr + DR[k]
                nc = cc + DC[k]
                if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
                    continue
                ncell = nr * cols + nc
                if grid[nr][nc] == '#' or ncell == obstacle:
                    continue
                if walk_seen[ncell] == walk_timer:
                    continue
                walk_seen[ncell] = walk_timer
                walk_dist[ncell] = cd + 1
                bfs_queue[tail] = ncell
                tail += 1
                if abs(nr - orow) + abs(nc - ocol) == 1:
                    found += 1

    INF = 10**18
    dist_push = [INF] * states
    dist_move = [INF] * states
    parent = [-2] * states
    parent_dir = [-1] * states
    pq = []

    def relax(st, new_pushes, new_moves, from_state, push_dir):
        if (
            new_pushes < dist_push[st]
            or (new_pushes == dist_push[st] and new_moves < dist_move[st])
        ):
            dist_push[st] = new_pushes
            dist_move[st] = new_moves
            parent[st] = from_state
            parent_dir[st] = push_dir
            heapq.heappush(pq, (new_pushes, new_moves, st))

    def try_pushes(box, keeper, from_state, base_pushes, base_moves):
        bfs_dist(keeper, box)
        brow = box // cols
        bcol = box % cols
        for d in range(4):
            wr = brow - DR[d]
            wc = bcol - DC[d]
            fr = brow + DR[d]
            fc = bcol + DC[d]
            if wr < 0 or wr >= rows or wc < 0 or wc >= cols:
                continue
            if fr < 0 or fr >= rows or fc < 0 or fc >= cols:
                continue
            if grid[wr][wc] == '#' or grid[fr][fc] == '#':
                continue
            behind = wr * cols + wc
            if walk_seen[behind] != walk_timer:
                continue
            new_box = fr * cols + fc
            new_state = new_box * 4 + OPP[d]
            relax(
                new_state,
                base_pushes + 1,
                base_moves + walk_dist[behind] + 1,
                from_state,
                d,
            )

    try_pushes(start_box, start_keeper, -1, 0, 0)
    goal_state = -1

    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
        keeper_r = box // cols + DR[side]
        keeper_c = box % cols + DC[side]
        keeper = keeper_r * cols + keeper_c
        try_pushes(box, keeper, st, pushes, moves)

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

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

    path_seen = [0] * cells
    path_parent = [-1] * cells
    path_parent_dir = [-1] * cells
    path_timer = 0

    def bfs_path(src, dst, 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
            cr = cur // cols
            cc = cur % cols
            for d in range(4):
                nr = cr + DR[d]
                nc = cc + DC[d]
                if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
                    continue
                ncell = nr * cols + nc
                if grid[nr][nc] == '#' or ncell == obstacle:
                    continue
                if path_seen[ncell] == path_timer:
                    continue
                path_seen[ncell] = path_timer
                path_parent[ncell] = cur
                path_parent_dir[ncell] = d
                bfs_queue[tail] = ncell
                tail += 1
        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:
        d = parent_dir[st]
        prev = parent[st]
        if prev == -1:
            prev_box = start_box
            prev_keeper = start_keeper
        else:
            prev_box = prev // 4
            prev_side = prev % 4
            prev_keeper = (
                (prev_box // cols + DR[prev_side]) * cols
                + (prev_box % cols + DC[prev_side])
            )
        behind = (
            (prev_box // cols - DR[d]) * cols
            + (prev_box % cols - DC[d])
        )
        answer.append(bfs_path(prev_keeper, behind, prev_box))
        answer.append(UPP[d])

    print(''.join(answer))


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