1138. Alphabet Board Path

题目描述

我们从一块字母板上的位置 (0, 0) 出发，该坐标对应的字符为 board[0][0]。

在本题里，字母板为board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"].

我们可以按下面的指令规则行动：

如果方格存在，'U' 意味着将我们的位置上移一行；
如果方格存在，'D' 意味着将我们的位置下移一行；
如果方格存在，'L' 意味着将我们的位置左移一列；
如果方格存在，'R' 意味着将我们的位置右移一列；
'!' 会把在我们当前位置 (r, c) 的字符 board[r][c] 添加到答案中。
返回指令序列，用最小的行动次数让答案和目标 target 相同。你可以返回任何达成目标的路径。

思路解析

该题可以有多种解题思路，1.最简单的就是将26个字母映射成一个map，将其坐标记录下来，然后
利用横纵坐标的变化实现对结果的输出。下面就是基于这种方法实现的代码，其很简单，主要就是map的映射，还有个就是在char声明一个字符数组的时候，C++ 编译器会在初始化数组时，自动把 ‘\0’ 放在字符串的末尾，所以这也是为什么开始我初始化的时候是初始的每列有6个，因为‘\0’占了哟个字符
2.第二个方法就是直接破解，把26个字符写成这样

Alphabet location.png

先创建一个字母板（二维字符数组），调整时把当前字符与目标字符减'A'，这样从'a'到'z'就变成了从0到25，然后先与下一个目标字符列对齐（两个字符减'a'后对5取余进行比较），然后再调整行对齐（两个字符减'a'后除以5进行比较），如果当前位置为'z'时，下一个目标字符若不是'z'则先将当前位置向上调整一步到'u'的位置，再继续进行相关调整。

下面是第一种方法的c++代码

#include<map>
#include<iostream>
#include<stdio.h>
#include<string>
#include<math.h>
#include <stdlib.h>
using namespace std;
class Solution {
public:
    string alphabetBoardPath(string target) {
        char maps[10][6]={"abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"};//将26个字母存入字符矩阵每行有5个
        map<char,pair<int,int> > matrix;//声明1个map来存储坐标位置与字符
        for(int i=0;i<6;i++)
            for(int j=0;j<5;j++)
             matrix[maps[i][j]]=make_pair(i,j);//将字母存入map中

        //record the initialization location
        int nx=0,ny=0;
        string out;
        for(int k=0;k<target.length();k++){
            int chx=nx-matrix[target[k]].first;//map中first与sencond的算法，first是pair中的第一个
            int chy=ny-matrix[target[k]].second;
           // cout<<chx<<" "<<chy<<endl;
            if(chx==0&&chy==0){
                out.push_back('!');//push_back是在字符串的最后加入一个字符串，vector中的方法
              //  out.append("!");这个string中的添加方法
            }
            else{
                if(chx>0){
                  for(int i=0;i<chx;i++)
                    out.push_back('U');
                }
                if(chy>0){
                  for(int i=0;i<chy;i++)
                    out.push_back('L');
                }
                if(chx<0){
                  for(int i=0;i<abs(chx);i++)
                    out.push_back('D');
                }

                if(chy<0){
                  for(int i=0;i<abs(chy);i++)
                    out.push_back('R');
                }
                 out.push_back('!');
            }
            nx=matrix[target[k]].first;
            ny=matrix[target[k]].second;
        }

        return out;
    }
};

int main(){
   Solution s;
   string target = "leet";
   string out1=s.alphabetBoardPath(target);
   cout<<out1;
}