AOJ : 1245 - Gap
問題概要
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1245
日本語訳をしてくださっていた方がいたので, そちらを参考にさせていただきました.
ありがとうございます.
http://bal4u.dip.jp/mt/program/2004/10/gap.html
プログラム
class P{ public: int cost; vector<int> v,pos,gap; P(){} P(int _cost,vector<int> _v,vector<int> _pos,vector<int> _gap){ cost = _cost; v = _v; pos = _pos; gap = _gap; } bool goal(){ } }; bool goal(vector<int> &v){ rep(i,4){ rep(j,7){ int idx = i * 8 + j; if(v[idx] / 10 != i + 1 || v[idx] % 10 != j + 1) return false; } } return true; } int bfs(P start){ queue<P> open; set<vector<int> > closed; open.push(start); closed.insert(start.v); while(!open.empty()){ P p = open.front(); open.pop(); rep(i,4){ vector<int> nv = p.v; vector<int> npos = p.pos; vector<int> ngap = p.gap; int idx = ngap[i]; int val = nv[idx-1] + 1; if(npos[val] == 0) continue; nv[idx] = val; nv[npos[val]] = 0; ngap[i] = npos[val]; npos[val] = idx; if(closed.find(nv) != closed.end()) continue; closed.insert(nv); if(goal(nv)){ return p.cost+1; } open.push(P(p.cost+1,nv,npos,ngap)); } } return -1; } int main(void){ int T; scanf("%d",&T); while(T--){ vector<int> v(32); vector<int> pos(50); vector<int> gap; rep(i,4){ rep(j,7){ int idx = i * 8 + j + 1; scanf("%d",&v[idx]); if(v[idx] % 10 == 1){ int row = v[idx] / 10 - 1; v[row*8] = v[idx]; v[idx] = 0; gap.push_back(idx); } else{ pos[v[idx]] = idx; } } } printf("%d\n",goal(v) ? 0 : bfs(P(0,v,pos,gap))); } }