[LeetCode]1138. Alphabet Board Path（第147周周赛）（模拟）

待我称王封你为后i 2021-11-16 13:28 288阅读 0赞

On an alphabet board, we start at position `(0, 0)`, corresponding to character `board[0][0]`.

Here, `board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"]`.

We may make the following moves:

*  `'U'` moves our position up one row, if the square exists;
 *  `'D'` moves our position down one row, if the square exists;
 *  `'L'` moves our position left one column, if the square exists;
 *  `'R'` moves our position right one column, if the square exists;
 *  `'!'` adds the character `board[r][c]` at our current position `(r, c)` to the answer.

Return a sequence of moves that makes our answer equal to `target` in the minimum number of moves. You may return any path that does so.

**Example 1:**

Input: target = "leet"
    Output: "DDR!UURRR!!DDD!"

**Example 2:**

Input: target = "code"
    Output: "RR!DDRR!UUL!R!"

**Constraints:**

*  `1 <= target.length <= 100`
 *  `target` consists only of English lowercase letters.

题目大意：

给出一个由字母排列成的矩阵，给出一个target，并且给出可以在矩阵中移动规则，从起始位置（0，0）出发经过最短的操作输出target。（注意，操作不能超出矩阵的范围）

解题思路：

首先考虑搜索，题目中给出上下左右操作就说明，可以来利用字母在矩阵中的坐标直接进行计算。

下一个字母的坐标-上一个字母的坐标，其x和y正负对应了上下左右操作，计算差值即可。

另外要注意若末位置为z则，不能首末位置直接相减。因为会超出边界，则我们可以将末位置先设为u，然后在结果中插入D即可。

class Solution {
    public:
        string alphabetBoardPath(string target) {
            vector<vector<int>> maps;
            for(int i=0;i<26;i++){
                vector<int> tmp_maps;
                tmp_maps.push_back(i/5);
                tmp_maps.push_back(i%5);
                maps.push_back(tmp_maps);
            }
            string ans="";
            int idx = 0, idy =0;
            for(int i=0;i<target.length();i++){
                int x = maps[target[i]-'a'][0]; 
                int y = maps[target[i]-'a'][1]; 
                
                int d_x = x - idx;
                int d_y = y - idy;
                
                if(d_x == 0 && d_y == 0){
                    ans = ans + '!';
                }else{
                    if(target[i] == 'z'){
                        d_x--;
                    }
                    int tt;
                    if(d_x<0){
                        tt = d_x * -1;
                        while(tt--){
                            ans = ans + 'U';
                        }
                    }else{
                        tt = d_x;
                        while(tt--){
                            ans = ans + 'D';
                        }
                    }
                    
                    if(d_y<0){
                        tt = d_y * -1;
                        while(tt--){
                            ans = ans + 'L';
                        }
                    }else{
                        tt = d_y;
                        while(tt--){
                            ans = ans + 'R';
                        }
                    }
                    if(target[i] == 'z'){
                        ans = ans +'D';
                    }
                    ans = ans + '!';
                }
                
                idx = x;
                idy = y;
            }
            return ans;
        }
    };