<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`

# Grid Maze

## Description

Given a $n×m$ grid maze which consists of walls (#), floors (.), start (A), and end(B). You can walk in four directions: up, down, left and right, but you cannot pass the walls. Please output a path to walk from the start to the end with minimum steps, or it is impossible to go from the start to the end.

## Input
The first line contains two integers nn and mm, being the number of rows and columns of the grid maze.

The following nn lines describes the maze. Each line has mm characters which is one of ==#==, ==.==, ==A==, or ==B==.

There is exactly one ==A== and ==B== in the input.

$1 \leq n, m \leq 10^3$

## Output
If it is possible to go from the start to the end, print "YES" in the first line, the number of minimum steps in the second line, and the path in the third line. Describe the path as a string consisting of characters L (left), R (right), U (up), and D (down). You can print any valid solution.

If it is impossible, please print "NO" in the first line.

## 解題思路
從A點做BFS到B點，並記錄每個點是從哪裡來的
### 時間複雜度 $O(n*m)$

## Code

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

struct Position {
	int row, column;
	char op;
	Position *pre;
	Position() {}
	Position(int _row_, int _column_, char _op_, Position *_pre_)
		: row(_row_), column(_column_), op(_op_), pre(_pre_) {}
};

int main() {
	int height, width;
	std::cin >> height >> width;
	std::vector<std::vector<Position>> grid(height, std::vector<Position>(width));
	Position *start, *end;
	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			std::cin >> grid[i][j].op;
			grid[i][j].row = i;
			grid[i][j].column = j;
			if (grid[i][j].op == 'A') start = &grid[i][j];
			if (grid[i][j].op == 'B') {
				end = &grid[i][j];
				grid[i][j].op = '.'; // for convenience
			}
		}
	}
	std::deque<Position*> dq;
	dq.emplace_back(start);
	while (!dq.empty()) {
		Position *f = dq.front();
		if (f == end) {
			std::string path;
			while (f != start) {
				path.push_back(f->op);
				f = f->pre;
			}
			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].op == '.') {
            grid[f->row - 1][f->column].pre = f;
            grid[f->row - 1][f->column].op = 'U';
			dq.emplace_back(&grid[f->row - 1][f->column]);
		}
		if (f->row + 1 < height && grid[f->row + 1][f->column].op == '.') {
			grid[f->row + 1][f->column].pre = f;
            grid[f->row + 1][f->column].op = 'D';
            dq.emplace_back(&grid[f->row + 1][f->column]);
		}
		if (f->column - 1 >= 0 && grid[f->row][f->column - 1].op == '.') {
			grid[f->row][f->column - 1].pre = f;
            grid[f->row][f->column - 1].op = 'L';
			dq.emplace_back(&grid[f->row][f->column - 1]);
		}
		if (f->column + 1 < width && grid[f->row][f->column + 1].op == '.') {
			grid[f->row][f->column + 1].pre = f;
            grid[f->row][f->column + 1].op = 'R';
			dq.emplace_back(&grid[f->row][f->column + 1]);
		}
		dq.pop_front();
	}
	std::cout << "NO" << std::endl;
	return 0;
}