public class Main { /** 存储输入的站位 */
static char[] rdm = new char[4];
/** 存储目标序列 */
static char[] dist = new char[8];
/** 存储目标序列的方向 */
static boolean distDirection;
/** 存储当前序列 */
static char[] map = new char[8];
/** 存储当前序列的方向 */
static boolean direction;
/** 目标序列的 code */
static int distCode;
public static void main(String[] args) throws IOException {
direction = read(map);
distDirection = read(dist);
distCode = getCode(dist, distDirection);
for (int i = 0; i != 4; ++i) {
rdm[i] = map[i] == '.' ? map[i + 4] : map[i];
}
if (!dfs())
System.out.print("None");
}
/** 移动顺序 */
static char[] moveOrder = {'W', 'G', 'C'};
/** 标记是否为第一次找到答案 */
static boolean nonFirst = false;
/** 标记指定序列是否访问过 */
static boolean[] record = new boolean[8200];
/** 存储路径 */
static Deque<Integer> list = new LinkedList<>();
static boolean dfs() {
int code = getCode(map, direction);
if (record[code] || !check()) return false;
list.add(code);
// 检查当前状态是否和目标状态相同
if (code == distCode) {
// 如果初始状态和目标状态相同，则直接返回 false
if (list.size() == 1) return false;
if (nonFirst) System.out.println();
else nonFirst = true;
for (int history : list) {
System.out.print(parseCode(history));
}
list.removeLast();
return true;
}
record[code] = true;
int offset = direction ? 4 : -4;
direction = !direction;
boolean result = false;
// 先尝试人单独过河
int mIndex = findIndex('M', offset);
map[mIndex] = '.';
map[mIndex + offset] = 'M';
if (dfs()) result = true;
else {
// 依次尝试人带一个过河
for (char value : moveOrder) {
int index = findIndex(value, offset);
if (index != -1) {
map[index] = '.';
map[index + offset] = value;
if (dfs()) result = true;
map[index] = value;
map[index + offset] = '.';
}
}
}
map[mIndex] = 'M';
map[mIndex + offset] = '.';
direction = !direction;
record[code] = false;
list.removeLast();
return result;
}
/** 检查当前序列是否合法 */
static boolean check() {
int offset = direction ? -4 : 4;
int w = findIndex('W', offset);
int g = findIndex('G', offset);
if (w != -1 && g != -1) return false;
int c = findIndex('C', offset);
return g == -1 || c == -1;
}
/** 在指定范围内查找下标 */
static int findIndex(char[] array, char dist, int left, int right) {
for (int i = left; i != right; ++i) {
if (array[i] == dist) return i;
}
return -1;
}
/**
* 在指定范围内查找目标下标
* @param dist 目标
* @param offset 4 表示在 [0, 4) 范围内查找，-4 表示在 [4, 8) 范围内查找
* @return 查找到返回下标，否则返回 -1
*/
static int findIndex(char dist, int offset) {
int left = offset == 4 ? 0 : 4;
return findIndex(map, dist, left, left + 4);
}
// 映射表
static char[] codeMap = {'M', 'W', 'G', 'C', '.'};
/** 将 code 转换为字符串 */
static String parseCode(int code) {
StringBuilder sb = new StringBuilder(14);
int[] parse = {
(code >> 9) & 7,
(code >> 6) & 7,
(code >> 3) & 7,
code & 7
};
for (int value : parse) {
sb.append(codeMap[value]);
}
sb.append((code >> 12) == 0 ? " <- " : " -> ");
for (int i = 0; i != parse.length; ++i) {
sb.append(parse[i] == 0b100 ? rdm[i] : '.');
}
sb.append("\n");
return sb.toString();
}
/** 将指定状态哈希化 */
static int getCode(char[] map, boolean direction) {
int result = direction ? 1 : 0;
for (int i = 0; i != 4; ++i) {
result = (result << 3) | findIndex(codeMap, map[i], 0, codeMap.length);
}
return result;
}
/**
* 读取一个状态
* @return 方向，true 向右，false 向左
*/
static boolean read(char[] map) throws IOException {
for (int i = 0; i != 4; ++i) map[i] = (char) System.in.read();
System.in.read();
boolean direction = System.in.read() == '-';
System.in.skip(2);
for (int i = 4; i != 8; ++i) map[i] = (char) System.in.read();
System.in.read();
return direction;
}
}
