<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:
    pair<int, int> position(char c){
        int flat = c - 'a';
        return make_pair(flat / 5, flat % 5);
    }
    
    int character(const pair<int, int>& pos){
        return pos.first * 5 + pos.second;
    }
    
    bool possible(const pair<int, int>& pos){
        return (pos.first >= 0 && pos.second >= 0 && pos.first < 5 && pos.second < 5) \
            || (pos.first == 5 && pos.second == 0);
    }
    
    string bfsPath(const pair<int, int>& begin, const pair<int, int>& end, vector<bool>& visited){
        struct node{
            pair<int, int> pos;
            string path;
        };
        
        struct pathInfo{
            pair<int, int> dir;
            char code;
        };
        
        array<pathInfo, 4> dirs ={
            pathInfo{make_pair(1, 0), 'D'},
            pathInfo{make_pair(-1, 0), 'U'},
            pathInfo{make_pair(0, 1), 'R'},
            pathInfo{make_pair(0, -1), 'L'},
        };
        
        queue<node> q;
        visited[character(begin)] = true;
        q.push(node{begin, ""});
        string path = "";
        while(!q.empty()){
            node n = q.front();
            q.pop();
            
            if(n.pos == end){
                path = n.path;
                break;
            }
            
            for(const auto& dir : dirs){
                auto next = make_pair(n.pos.first + dir.dir.first, n.pos.second + dir.dir.second);
                if(!possible(next)){
                    continue;
                }
                
                if(!visited[character(next)]){
                    visited[character(next)] = true;
                    q.push(node{next, n.path + dir.code});
                }
            }    
        }
        
        return path + "!";
    }
    
    string alphabetBoardPath(string target) {
        auto begin = position('a');
        string ans = "";
        for(int i = 0; i < target.size(); ++i){
            auto end = position(target[i]);
            vector<bool> visited(26, false);
            ans += bfsPath(begin, end, visited);
            begin = end;
        }
        return ans;
    }
};
12700