【AOJ ALDS1_13】B: Heuristic Search - 8 Puzzle
問題
| アルゴリズムとデータ構造 | Aizu Online Judge
方針
- DFSをして正しい並びになったかを判定し, その時のターン数を返す.
- 探索した盤面はフラグを立てておき, 同じ状態を2回以上探索しないようにする.
- mapって比較の"<“が定義されてないと使えないのを初めて知った.
コード
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<ctime> #include<cctype> #include<climits> #include<iostream> #include<string> #include<vector> #include<map> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<memory> #include<functional> #define rep(i, n) REP(i, 0, n) #define REP(i, a, n) for(int i = a ; i < (int)n ; i++) using namespace std; int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; struct Puzzle{ int field[9]; int space; int turn; bool operator < (const Puzzle& a) const{ rep(i, 9){ if(a.field[i] == field[i]) continue; return field[i] > a.field[i]; } return false; } }; bool check(Puzzle p){ rep(i, 9){ if(p.field[i] != i+1) return false; } return true; } int solve(Puzzle in){ queue<Puzzle> q; map<Puzzle, bool> mp; q.push(in); mp[in] = true; // bfs while(!q.empty()){ Puzzle p = q.front(); q.pop(); if(check(p)) return p.turn; int x = p.space % 3; int y = p.space / 3; rep(i, 4){ int nx = x + dx[i]; int ny = y + dy[i]; if(nx < 0 || 2 < nx || ny < 0 || 2 < ny) continue; Puzzle tmp = p; swap(tmp.field[p.space], tmp.field[3 * ny + nx]); tmp.space = 3 * ny + nx; if(mp[tmp] == false){ mp[tmp] = true; tmp.turn++; q.push(tmp); } } } return -1; } signed main(){ Puzzle in; rep(i, 9){ cin >> in.field[i]; if(in.field[i] == 0){ in.field[i] = 9; in.space = i; } } in.turn = 0; cout << solve(in) << endl; }