<style>
html, body, .ui-content {
background-image: url(https://truth.bahamut.com.tw/s01/201508/7f0e4bd0e01135c9df434733e0d1544a.JPG);
background-color: #333;
color: #DDD;
}
</style>

###### tags: `Meowmeow Online Judge`

# Monsters
## Description

You and some monsters are in a labyrinth. When taking a step to some direction in the labyrinth, each monster may simultaneously take one as well. Your goal is to reach one of the boundary squares without ever sharing a square with a monster.

Your task is to find out if your goal is possible, and if it is, print a path that you can follow. Your plan has to work in any situation; even if the monsters know your path beforehand.

# Input
The first input line has two integers $n$ and $m$: the height and width of the map.

After this there are n lines of m characters describing the map. Each character is . (floor), # (wall), A (start), or M (monster). There is exactly one A in the input.

$10001≤n,m≤1000$
# Output
First print "YES" if your goal is possible, and "NO" otherwise.

If your goal is possible, also print an example of a valid path (the length of the path and its description using characters D, U, L, and R). You can print any path, as long as its length is at most $n⋅m$ steps.

## 解題思路
用這些條件下去BFS
1. Monster走過的點都不能再走
2. 自己走過的點也不能再走
3. 每回合Monster先走，自己才不會碰到Monster

先把Monster丟進queue中，再把自己丟進去，維持兩者都在相同回合

## Code

#include <algorithm>
#include <deque>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

struct Position {
	int row, column;
	char status;
	char op;
	Position *prev;
	Position() {}
};

int main() {
	int height, width;
	std::cin >> height >> width;
	std::vector<std::vector<Position>> grid(height, std::vector<Position>(width));
	std::deque<Position*> dq;
	Position *start;

	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			std::cin >> grid[i][j].status;
			grid[i][j].row = i;
			grid[i][j].column = j;
			if (grid[i][j].status == 'A') start = &grid[i][j];
			if (grid[i][j].status == 'M') dq.emplace_back(&grid[i][j]);
		}
	}
	dq.emplace_back(start);
	while (!dq.empty()) {
		Position *f = dq.front();
		// if (f->status == 'A') std::cout << f->row << ',' << f->column << std::endl;
		if (f->status == 'A' && (f->row == 0 || f->row == height - 1 || f->column == 0 || f->column == width - 1)) {
			std::string path;
			while (f != start) {
				path.push_back(f->op);
				f = f->prev;
			}
			std::reverse(path.begin(), path.end());
			std::cout << "YES\n"
					  << path.length() << '\n'
					  << path << std::endl;
			return 0;
		}
		if (f->row - 1 >= 0 && grid[f->row - 1][f->column].status == '.') {
            grid[f->row - 1][f->column].prev = f;
            grid[f->row - 1][f->column].op = 'U';
			grid[f->row - 1][f->column].status = f->status;
			dq.emplace_back(&grid[f->row - 1][f->column]);
		}
		if (f->row + 1 < height && grid[f->row + 1][f->column].status == '.') {
			grid[f->row + 1][f->column].prev = f;
            grid[f->row + 1][f->column].op = 'D';
			grid[f->row + 1][f->column].status = f->status;
            dq.emplace_back(&grid[f->row + 1][f->column]);
		}
		if (f->column - 1 >= 0 && grid[f->row][f->column - 1].status == '.') {
			grid[f->row][f->column - 1].prev = f;
            grid[f->row][f->column - 1].op = 'L';
			grid[f->row][f->column - 1].status = f->status;
			dq.emplace_back(&grid[f->row][f->column - 1]);
		}
		if (f->column + 1 < width && grid[f->row][f->column + 1].status == '.') {
			grid[f->row][f->column + 1].prev = f;
            grid[f->row][f->column + 1].op = 'R';
			grid[f->row][f->column + 1].status = f->status;
			dq.emplace_back(&grid[f->row][f->column + 1]);
		}
		dq.pop_front();
	}
	std::cout << "NO" << std::endl;
	return 0;
}