773. Sliding Puzzle

773. Sliding Puzzle

source

Topic: BFS

Time Complexity: (n*m)!

Solution 01

class Solution{
public:
  int slidingPuzzle (vector<vector<int>>& board)
  {
    constexpr int row = 2;
    constexpr int col = 3;
    string goal, start;
    for(int i = 0; i  < board.size(); i++)
      for(int j = 0; j < board[0].size(); j++){
        start += (board[i][j] + '0');
        goal += (i*col + j + 1) % (row*col) + '0';//12345.....0
      }
      if (start == goal) return 0;

      constexpr int dirs[4][2] = {{-1,0}, {1,0}, {0,1}, {0, -1}};

      set<string> visited{start};
      int steps = 0;
      queue<string>Q;
      Q.push(start);
      while (!Q.empty()){
        steps++;
        int sz = Q.size();
        while(sz-- > 0){
        string s = Q.front();
        Q.pop();
        int p = s.find('0');
        int y = p/col;
        int x = p%col;
        for(int i = 0; i < 4; i++){
          int tx = x + dirs[i][0];
          int ty = y + dirs[i][1];
          if(tx < 0 || ty < 0 || tx >= col || ty >= row) continue;
          int pp = ty * col + tx;
          string t(s);
          swap(t[p], t[pp]);
          if(visited.count(t))continue;
          if(t == goal) return steps;
          visited.insert(t);
          Q.push(t);
         }  
        }
      }
      return -1;
  }
};

 

Solution 02

             Simplified, only works on 3×2 board

class Solution
{
public:
    int slidingPuzzle (vector<vector<int>> & board){
        const string goal = "123450";
        string start;
        for(int i = 0; i < board.size(); i++)
            for(int j = 0; j < board[0].size(); j++)
                start += (board[i][j] + '0');

            if(start == goal)return 0;

            const vector<vector<int>> idx{{1,3}, {0,2,4}, {1,5}, {0,4}, {1,3,5}, {2,4}};

            set<string> visited{start};
            int steps = 0;
            queue<pair<string,int>> Q;
            Q.emplace(start, start.find('0'));
            while(!Q.empty())
            {
                steps++;
                int sz = Q.size();
                while(sz-- > 0){
                    const auto& p = Q.front();
                    Q.pop();
                    for(int index: idx[p.second]){
                        string t(p.first);
                        swap(t[p.second], t[index])
                        if(visited.count(t))continue;
                        if(t == goal)return steps;
                        visited.insert(t);
                        Q.emplace(t, index);
                    }
                }
            }
            return -1;
    }
   
};

Share: