8パズル aoj 幅優先探索 alds1_13_b

ALDS1_13_B 8パズル

ALDS1_13_B 8 パズル
Feb. 2, 2020, 1:52 p.m.

目次

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_13_B

解説

パズルの盤面を状態とみなして、可能な状態遷移を繰り返して目標とする盤面となるまでの最短遷移回数が問題の答え.
最短距離を求める問題なので、幅優先探索で状態変化をたどる.
最初に見つかった答えがそのまま最短距離となる.
すでに調べた盤面はハッシュテーブルなどで管理し無駄な計算を省く.

解答1

ハッシュテーブルバージョン

この問題の場合Puzzle構造体のハッシュのために$O(N)$、ハッシュを使ってのアクセスは$O(1)$なので、Puzzle構造体をキーとしたアクセスは$O(N)$.
マップ(二分探索木)の場合はソートされるので、全要素の比較に$O(N)$、アクセスに$O(\log N)$なので、$O(N\times\log N)$.ハッシュテーブルが有利。

(※$N = 8$)

  • 時間: 20s
  • メモリ: 41252KB
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#define N 3
#define NN (N*N)

vector<Int> dx = {0, 0, -1, 1};
vector<Int> dy = {-1, 1, 0, 0};
vector<char> dirs = {'u', 'd', 'l', 'r'};


struct Puzzle {
  vector<Int> vec;
  Int blank;
  string path;

  Puzzle(): vec(NN, -1), blank(-1), path("") {
  }

  Puzzle(vector<Int> &vec, Int blank, string path) {
    this->vec = vec;
    this->blank = blank;
    this->path = path;
  }

  bool operator == (const Puzzle &other) const { 
    loop(n,0,NN) {
      if (vec[n] != other.vec[n]) return false;
    }

    return true;
  }

  Puzzle move(Int dir) {
    // i = h * N + w
    Int sx = blank % N;
    Int sy = blank / N;
    Int tx, ty;

    switch (dir) {
      case 0: 
      case 1:
      case 2:
      case 3:
        tx = sx + dx[dir];
        ty = sy + dy[dir];
        break;
      default:
        cout << "Invalid dir: " << dir << endl;
        exit(1);
        break;
    }

    Puzzle p;
    if (tx < 0 || N <= tx || ty < 0 || N <= ty) {
      return p;
    }

    p = *this;
    swap(p.vec[sy * N + sx], p.vec[ty * N + tx]);
    p.blank = ty * N + tx;
    p.path += dirs[dir];
    return p;
  }

  void dump() {
    loop(n,0,NN) cout << vec[n] << ' '; cout << endl;
  }

  void dump2() {
    loop(h,0,N) {
      loop(w,0,N) {
        cout << vec[h * N + w] << ' ';
      }
      cout << endl;
    }
  }
};

namespace std {

  template <>
  struct hash<Puzzle>
  {
    std::size_t operator()(const Puzzle& p) const
    {
      std::size_t seed = p.vec.size();
      for(auto& i : p.vec) {
        seed ^= i + 0x9e3779b9 + (seed << 6) + (seed >> 2);
      }
      return seed;
    }
  };
}


vector<Int> targetVec = {1, 2, 3, 4, 5, 6, 7, 8, 0};
Puzzle target(targetVec, 8, "");
Puzzle source;


Int bfs() {
  queue<Puzzle> Q;
  unordered_map<Puzzle, bool> DONE;

  Q.push(source);
  DONE[source] = true;

  while (!Q.empty()) {
    Puzzle top = Q.front(); Q.pop();
    if (top == target) return top.path.length();

    loop(dir,0,dirs.size()) {
      Puzzle p = top.move(dir);
      if (p.blank== -1) continue; // Invalid board
      if (DONE[p]) continue;
      Q.push(p);
      DONE[p] = true;
    }
  }

  cout << "No solution" << endl;
  return -1;
}

void input() {
  vector<Int> vec(NN, -1);
  Int blank = -1;
  loop(h,0,N) {
    loop(w,0,N) {
      cin >> vec[h*N + w];
      if (vec[h*N + w] == 0) blank = h * N + w;
    }
  }
  source.vec = vec;
  source.blank = blank;
}

void solve() {
  cout << bfs() << endl;
}


int main() {
  input();
  solve();
}

解答2

マップ(二分探索木バージョン)

  • 時間: 32s
  • メモリ: 42392KB

(差分のみ掲載)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
// mapのためにPuzzle構造体に<を定義
struct Puzzle {
  ...省略...
  bool operator < (const Puzzle &other) const {
    loop(n,0,NN) {
      if (vec[n] == other.vec[n]) continue;
      return vec[n] > other.vec[n];
    }

    return false;
  }
  ...省略...
};

Int bfs() {
  ...省略...
  map<Puzzle, bool> DONE; // unordered_mapの代わりにmapを使用
  ...省略...
}