Advertisement
ambition-xx

bfs

Jan 13th, 2022 (edited)
676
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.90 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <set>
  5. #include <queue>
  6. using namespace std;
  7. int step = 0;
  8. // 每次要不就是和左边交换要不就是和右边交换
  9. int dirs[4] = {-2, -1, 1, 2};
  10. void bfs(string source, string target){
  11.     queue<string> q;
  12.     set<string> visited;
  13.     q.push(source);
  14.     visited.insert(source);
  15.     while(!q.empty()){
  16.         step += 1;
  17.         int qsize = q.size();
  18.         for(int i = 0; i < qsize; i++){
  19.             string t = q.front();
  20.             q.pop();
  21.             if(t == target) return;
  22.             int pos = t.find(' ');
  23.             for(int i = 0; i < 4; i++){
  24.                 string next = t;
  25.                 swap(next[(pos + dirs[i] + 9) % 9], next[pos]);
  26.                 if(visited.count(next)){
  27.                     continue;
  28.                 }
  29.                 cout << next << endl;
  30.                 q.push(next);
  31.                 visited.insert(next);
  32.             }
  33.         }
  34.     }
  35. }
  36. int main(){
  37.     // 空格代表空盘子
  38.     bfs("12345678 ", "87654321 ");
  39.     cout << step << endl;
  40.     return 0;
  41. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement