SRM425 div1 medium
しんどい。
やることはただのBFS。でも状態をmapでメモしとかないと無限ループに落ちる。
#include <string> #include <vector> #include <queue> #include <map> using namespace std; int mv[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; class PiecesMover { public: int nP; bool check(vector<int> pos) { vector<string> board(5,string(5,'.')); for(int i=0;i<nP;i++) board[pos[i]/5][pos[i]%5]='*'; int connected=0; queue<int> que; que.push((pos[0]/5)*5+pos[0]%5); while(!que.empty()) { int y=que.front()/5,x=que.front()%5; que.pop(); if(board[y][x]!='*') continue; connected++; board[y][x]='#'; for(int i=0;i<4;i++) { int yy=y+mv[i][0],xx=x+mv[i][1]; if(yy<0 || 4<yy || xx<0 || 4<xx) continue; que.push(yy*5+xx); } } return (connected==nP); } int getMinimumMoves(vector <string> board) { nP=0; vector<int> first; for(int i=0;i<5;i++) for(int j=0;j<5;j++) if(board[i][j]=='*') first.push_back(i*5+j),nP++; map<vector<int>,int> used; queue<pair<vector<int>,int> > que; que.push(make_pair(first,0)); while(!que.empty()) { vector<int> v=que.front().first; int d=que.front().second; que.pop(); if(used.find(v)!=used.end()) continue; else if(check(v)) return d; else { used[v]=d; for(int i=0;i<nP;i++) for(int j=0;j<4;j++) { vector<int> vv=v; int y=vv[i]/5+mv[j][0],x=vv[i]%5+mv[j][1]; if(y<0 || 4<y || x<0 || 4<x) continue; vv[i]=y*5+x; int k; for(k=0;k<nP;k++) if(k!=i && vv[i]==vv[k]) break; if(k==nP) que.push(make_pair(vv,d+1)); } } } return -1; } };