<p>On an alphabet board, we start at position <code>(0, 0)</code>, corresponding to character&nbsp;<code>board[0][0]</code>.</p>

<p>Here, <code>board = [&quot;abcde&quot;, &quot;fghij&quot;, &quot;klmno&quot;, &quot;pqrst&quot;, &quot;uvwxy&quot;, &quot;z&quot;]</code>, as shown in the diagram below.</p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2019/07/28/azboard.png" style="width: 250px; height: 317px;" /></p>

<p>We may make the following moves:</p>

<ul>
	<li><code>&#39;U&#39;</code> moves our position up one row, if the position exists on the board;</li>
	<li><code>&#39;D&#39;</code> moves our position down one row, if the position exists on the board;</li>
	<li><code>&#39;L&#39;</code> moves our position left one column, if the position exists on the board;</li>
	<li><code>&#39;R&#39;</code> moves our position right one column, if the position exists on the board;</li>
	<li><code>&#39;!&#39;</code>&nbsp;adds the character <code>board[r][c]</code> at our current position <code>(r, c)</code>&nbsp;to the&nbsp;answer.</li>
</ul>

<p>(Here, the only positions that exist on the board are positions with letters on them.)</p>

<p>Return a sequence of moves that makes our answer equal to <code>target</code>&nbsp;in the minimum number of moves.&nbsp; You may return any path that does so.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> target = "leet"
<strong>Output:</strong> "DDR!UURRR!!DDD!"
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> target = "code"
<strong>Output:</strong> "RR!DDRR!UUL!R!"
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= target.length &lt;= 100</code></li>
	<li><code>target</code> consists only of English lowercase letters.</li>
</ul>
class Solution {
public:
    string alphabetBoardPath(string target) {
        string answer = "";
        char prev = 'a';
        for (char c : target) {
            answer += moveBoard(prev, c);
            prev = c;
        }        
        return answer;
    }
private:
    pair<int, int> charToRowCol(char c) {
        int distance = c - 'a';
        int row = distance / 5;
        int col = distance % 5;
        return make_pair(row, col);
    }
    string moveBoard(char start, char target) {
        auto [start_row, start_col] = charToRowCol(start);
        auto [target_row, target_col] = charToRowCol(target);

        // to deal with the missing area after 'z'
        // if go left-down; left first then down
        // if go right-up; up first then right
        if (start_col > target_col && start_row < target_row) {
            // left first, then down
            string go_left = string(start_col - target_col, 'L');
            string go_down = string(target_row - start_row, 'D');
            return go_left + go_down + "!";
        } else {
            // vertical first, then horizontal
            string go_vertical;
            string go_horizontal;
            if (start_row < target_row) {
                go_vertical = string(target_row - start_row, 'D');
            } else {
                go_vertical = string(start_row - target_row, 'U');
            }
            if (start_col < target_col) {
                go_horizontal = string(target_col - start_col, 'R');
            } else {
                go_horizontal = string(start_col - target_col, 'L');
            }
            return go_vertical + go_horizontal + "!";
        }
    }
};
9000