{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"Bloxorz是一个风靡世界的小游戏。\n\nBloxorz的地图是一个N行M列的矩阵,每个位置可能是硬地(用.表示)、易碎地面(用E表示)、禁地(用#表示)、起点(用X表示)或终点(用O表示)。\n\n你的任务是操作一个$1\\*1\\*2$的长方体。这个长方体在地面上有两种放置形式,“立”在地面上($1\\*1$的面接触地面)或者“躺”在地面上($1\\*2$的面接触地面)。\n\n在每一步操作中,可以按上下左右四个键之一。按下之后,长方体向对应的方向沿着棱滚动90度。\n\n任意时刻,长方体不能有任何部位接触禁地(否则就会掉下去),并且不能立在易碎地面上(否则会因为压强太大掉下去)。\n\nX标识长方体的起始位置,地图上可能有一个X或者两个相邻的X。\n\n地图上唯一的一个O标识目标位置。求把长方体移动到目标位置(即立在O上)所需要的最少步数。如果无解,输出Impossible。在移动过程中,X和O标识的位置都可以看作是硬地被利用,$3\u003c\u003dN,M\u003c\u003d500$。"}},{"title":"Input","value":{"format":"MD","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\u003cp\u003eInput contains multiple test cases. Each test case is one single stage of the game. It starts with two integers \u003ci\u003eN\u003c/i\u003e and \u003ci\u003eM\u003c/i\u003e(3 ≤ N, M ≤ 500) which stands for number of rows and columns of the plane. That follows the plane, which contains \u003ci\u003eN\u003c/i\u003e lines and \u003ci\u003eM\u003c/i\u003e characters for each line, with \u0027O\u0027 (Oh) for target cell, \u0027X\u0027 for initial position of the box, \u0027.\u0027 for a rigid cell, \u0027#\u0027 for a empty cell and \u0027E\u0027 for a easily broken cell. A test cases starts with two zeros ends the input.\u003c/p\u003e\u003cp\u003eIt guarantees that \u003c/p\u003e\u003cul\u003e\u003cli\u003eThere\u0027s only one \u0027O\u0027 in a plane.\u003c/li\u003e\u003cli\u003eThere\u0027s either one \u0027X\u0027 or neighbouring two \u0027X\u0027s in a plane.\u003c/li\u003e\u003cli\u003eThe first(and last) row(and column) must be \u0027#\u0027(empty cell).\u003c/li\u003e\u003cli\u003eCells covered by \u0027O\u0027 and \u0027X\u0027 are all rigid cells.\u003c/li\u003e\u003c/ul\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"MD","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\u003cp\u003eFor each test cases output one line with the minimum number of moves or \"Impossible\" (without quote) when there\u0027s no way to achieve the target cell. \u003c/p\u003e\u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"MD","content":"\u003cpre class\u003d\"sio\"\u003e7 7\n#######\n#..X###\n#..##O#\n#....E#\n#....E#\n#.....#\n#######\n0 0\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"MD","content":"\u003cpre class\u003d\"sio\"\u003e10\u003c/pre\u003e"}}]}