UVA589 Pushing Boxes

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

#define dbg(...) cerr << "[" << #__VA_ARGS__ << "] = ", debug_out(__VA_ARGS__)
template <typename T> void debug_out(T t) { cerr << t << endl; }
template <typename T, typename... Ts> void debug_out(T t, Ts... ts) {
	cerr << t << ", ";
	debug_out(ts...);
}


int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, m;
	while (cin >> n >> m && n) {
		vector<vector<char>> a(n + 2, vector<char>(m + 2, '#'));
		vector<vector<vector<int>>> f(
			n + 2, vector<vector<int>>(m + 2, vector<int>(3, 1e9)));
		using S = tuple<int, int, int>;
		S st, ed;
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= m; ++j) {
				cin >> a[i][j];
				if (a[i][j] == 'X' && st == make_tuple(0, 0, 0)) {
					st = {i, j, 0};
					a[i][j] = '.';
				}
				if (a[i][j] == 'O') {
					ed = {i, j, 0};
					a[i][j] = '.';
				}
			}
		}
		{
			auto &[sx, sy, sz] = st;
			if (a[sx][sy + 1] == 'X') {
				sz = 1;
				a[sx][sy + 1] = '.';
			} else if (a[sx + 1][sy] == 'X') {
				sz = 2;
				a[sx + 1][sy] = '.';
			}
			f[sx][sy][sz] = 0;
		}
		queue<S> q;
		q.push(st);
		const int fx[3][4] = {{0, -2, 0, 1}, {0, -1, 0, 1}, {0, -1, 0, 2}};
		const int fy[3][4] = {{-2, 0, 1, 0}, {-1, 0, 2, 0}, {-1, 0, 1, 0}};
		const int fz[3][4] = {{1, 2, 1, 2}, {0, 1, 0, 1}, {2, 0, 2, 0}};
		auto check = [&](int x, int y, int z) {
			if (x < 1 || x > n || y < 1 || y > m) return 1;
			if (a[x][y] == '#') return 1;
			if (z == 0 && a[x][y] != '.') return 1;
			if (z == 1 && a[x][y + 1] == '#') return 1;
			if (z == 2 && a[x + 1][y] == '#') return 1;
			return 0;
		};
		while (!q.empty()) {
			if (ed == q.front()) break;
			auto [x, y, z] = q.front();
			q.pop();
			for (int i = 0; i < 4; ++i) {
				int nx = x + fx[z][i], ny = y + fy[z][i], nz = fz[z][i];
				if (check(nx, ny, nz)) continue;
				if (f[nx][ny][nz] == 1e9) {
					f[nx][ny][nz] = f[x][y][z] + 1;
					q.push({nx, ny, nz});
				}
			}
		}
		{
			auto [ex, ey, ez] = ed;
			if (f[ex][ey][ez] != 1e9)
				cout << f[ex][ey][ez] << endl;
			else
				cout << "Impossible" << endl;
		}
	}
	return 0;
}