<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:
    void dfs(int x, int y, int i, string &s, unordered_map<char, vector<int>> &mp, string &ans){
        // cout<<x<<" "<<y<<" "<<i<<" "<<s[i]<<endl;
        if(mp[s[i]] == vector<int>{x, y}){
            ans.push_back('!');
            i++;
        }
        // cout<<ans<<endl;
        int n=s.size();
        if(i == n){
            return;
        }
        int new_x=mp[s[i]][0], new_y=mp[s[i]][1];
        if(x < new_x and (x+1<5 or y ==0)){
            ans.push_back('D');
            dfs(x+1, y, i, s, mp, ans);
            return;
        }else if(x>new_x){
            ans.push_back('U');
            dfs(x-1, y, i, s, mp, ans);
            return;
        }
        if(y < new_y){
            ans.push_back('R');
            dfs(x, y+1, i, s, mp, ans);
            return;
        }else if(y>new_y){
            ans.push_back('L');
            dfs(x, y-1, i, s, mp, ans);
            return;
        }dfs(x, y, i, s, mp, ans);
    }
    string alphabetBoardPath(string s) {
        unordered_map<char, vector<int>> mp;
        char c='a';
        for(int i=0, cnt=0; i<6 and cnt<26; i++){
            for(int j=0; j<5 and cnt<26; j++){
                mp[c++] = {i, j};
            }
        }
        string ans;
        dfs(0, 0, 0, s, mp, ans);
        return ans;
    }
};
9700