力扣 773. 滑动谜题 bfs \ A*

https://leetcode-cn.com/problems/sliding-puzzle/

思路：本质上还是bfs……但是数组不好计算哈希，我们可以把它转换为字符串，即按照从左到右、从上到下的顺序连接起来。这样交换操作和哈希操作都比较容易执行。

class Solution {
public:

    string getStr(const vector<vector<int>>& board)
    {
        string s;
        for(int i=0;i<2;i++)
            for(int j=0;j<3;j++)
                s+=board[i][j]+'0';
        return move(s);
    }

    int slidingPuzzle(vector<vector<int>>& board) {
        string target="123450",begin=getStr(board);
        if(begin==target)
            return 0;
        int dir[4]={1,3,-1,-3};
        unordered_map<string,int> step;
        queue<string> q;
        q.push(begin);
        step[begin]=0;
        while(!q.empty())
        {
            string s=move(q.front());
            q.pop();
            int pos=s.find('0');
            for(int i=0;i<4;i++)
            {
                if((pos==2&&i==0)||(pos==3&&i==2))
                    continue;
                int npos=pos+dir[i];
                if(npos>=0&&npos<6)
                {
                    string tmp=s;
                    swap(tmp[pos],tmp[npos]);
                    if(!step.count(tmp))
                    {
                        if(tmp==target)
                            return step[s]+1;
                        step[tmp]=step[s]+1;
                        q.push(move(tmp));
                    }
                }
            }
        }
        return -1;
    }
};

思路：这道题也可以用A*来做，预估函数可以使用每个位置的数字到目标位置的曼哈顿距离。不过懒得写了orz。

最后

以上就是优秀天空最近收集整理的关于力扣 773. 滑动谜题 bfs \ A*的全部内容，更多相关力扣内容请搜索靠谱客的其他文章。