こういう実装が大の苦手なので、無工夫です。本当にしんでしまいそうです。*1
中身はBFSするだけです。
#include<vector> #include<queue> #include<algorithm> #include<string> using namespace std; class CornersGame{ public: int bfs[36][36][36][36]; int countMoves(vector<string> a){ queue<pair<pair<int,int>,pair<int,int> > > Q; for(int i=0;i<36;i++) for(int j=0;j<36;j++) for(int k=0;k<36;k++) for(int l=0;l<36;l++) bfs[i][j][k][l]=-1; bfs[28][29][34][35]=0; Q.push(make_pair(make_pair(28,29),make_pair(34,35))); while(Q.size()){ int one=Q.front().first.first; int two=Q.front().first.second; int three=Q.front().second.first; int four=Q.front().second.second; a[one/6][one%6]='s'; a[two/6][two%6]='s'; a[three/6][three%6]='s'; a[four/6][four%6]='s'; Q.pop(); if(one==two||one==three||one==four||two==three||two==four||three==four)continue; if(one%6>0&&a[one/6][one%6-1]=='.'&&bfs[one-1][two][three][four]==-1){ bfs[one-1][two][three][four]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one-1,two),make_pair(three,four))); } if(one%6>1&&a[one/6][one%6-1]=='s'&&a[one/6][one%6-2]=='.'&&bfs[one-2][two][three][four]==-1){ bfs[one-2][two][three][four]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one-2,two),make_pair(three,four))); } if(one%6<5&&a[one/6][one%6+1]=='.'&&bfs[one+1][two][three][four]==-1){ bfs[one+1][two][three][four]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one+1,two),make_pair(three,four))); } if(one%6<4&&a[one/6][one%6+1]=='s'&&a[one/6][one%6+2]=='.'&&bfs[one+2][two][three][four]==-1){ bfs[one+2][two][three][four]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one+2,two),make_pair(three,four))); } if(one/6>0&&a[one/6-1][one%6]=='.'&&bfs[one-6][two][three][four]==-1){ bfs[one-6][two][three][four]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one-6,two),make_pair(three,four))); } if(one/6>1&&a[one/6-1][one%6]=='s'&&a[one/6-2][one%6]=='.'&&bfs[one-12][two][three][four]==-1){ bfs[one-12][two][three][four]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one-12,two),make_pair(three,four))); } if(one/6<5&&a[one/6+1][one%6]=='.'&&bfs[one+6][two][three][four]==-1){ bfs[one+6][two][three][four]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one+6,two),make_pair(three,four))); } if(one/6<4&&a[one/6+1][one%6]=='s'&&a[one/6+2][one%6]=='.'&&bfs[one+12][two][three][four]==-1){ bfs[one+12][two][three][four]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one+12,two),make_pair(three,four))); } // if(two%6>0&&a[two/6][two%6-1]=='.'&&bfs[one][two-1][three][four]==-1){ bfs[one][two-1][three][four]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one,two-1),make_pair(three,four))); } if(two%6>1&&a[two/6][two%6-1]=='s'&&a[two/6][two%6-2]=='.'&&bfs[one][two-2][three][four]==-1){ bfs[one][two-2][three][four]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one,two-2),make_pair(three,four))); } if(two%6<5&&a[two/6][two%6+1]=='.'&&bfs[one][two+1][three][four]==-1){ bfs[one][two+1][three][four]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one,two+1),make_pair(three,four))); } if(two%6<4&&a[two/6][two%6+1]=='s'&&a[two/6][two%6+2]=='.'&&bfs[one][two+2][three][four]==-1){ bfs[one][two+2][three][four]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one,two+2),make_pair(three,four))); } if(two/6>0&&a[two/6-1][two%6]=='.'&&bfs[one][two-6][three][four]==-1){ bfs[one][two-6][three][four]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one,two-6),make_pair(three,four))); } if(two/6>1&&a[two/6-1][two%6]=='s'&&a[two/6-2][two%6]=='.'&&bfs[one][two-12][three][four]==-1){ bfs[one][two-12][three][four]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one,two-12),make_pair(three,four))); } if(two/6<5&&a[two/6+1][two%6]=='.'&&bfs[one][two+6][three][four]==-1){ bfs[one][two+6][three][four]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one,two+6),make_pair(three,four))); } if(two/6<4&&a[two/6+1][two%6]=='s'&&a[two/6+2][two%6]=='.'&&bfs[one][two+12][three][four]==-1){ bfs[one][two+12][three][four]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one,two+12),make_pair(three,four))); } // if(three%6>0&&a[three/6][three%6-1]=='.'&&bfs[one][two][three-1][four]==-1){ bfs[one][two][three-1][four]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one,two),make_pair(three-1,four))); } if(three%6>1&&a[three/6][three%6-1]=='s'&&a[three/6][three%6-2]=='.'&&bfs[one][two][three-2][four]==-1){ bfs[one][two][three-2][four]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one,two),make_pair(three-2,four))); } if(three%6<5&&a[three/6][three%6+1]=='.'&&bfs[one][two][three+1][four]==-1){ bfs[one][two][three+1][four]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one,two),make_pair(three+1,four))); } if(three%6<4&&a[three/6][three%6+1]=='s'&&a[three/6][three%6+2]=='.'&&bfs[one][two][three+2][four]==-1){ bfs[one][two][three+2][four]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one,two),make_pair(three+2,four))); } if(three/6>0&&a[three/6-1][three%6]=='.'&&bfs[one][two][three-6][four]==-1){ bfs[one][two][three-6][four]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one,two),make_pair(three-6,four))); } if(three/6>1&&a[three/6-1][three%6]=='s'&&a[three/6-2][three%6]=='.'&&bfs[one][two][three-12][four]==-1){ bfs[one][two][three-12][four]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one,two),make_pair(three-12,four))); } if(three/6<5&&a[three/6+1][three%6]=='.'&&bfs[one][two][three+6][four]==-1){ bfs[one][two][three+6][four]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one,two),make_pair(three+6,four))); } if(three/6<4&&a[three/6+1][three%6]=='s'&&a[three/6+2][three%6]=='.'&&bfs[one][two][three+12][four]==-1){ bfs[one][two][three+12][four]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one,two),make_pair(three+12,four))); } // if(four%6>0&&a[four/6][four%6-1]=='.'&&bfs[one][two][three][four-1]==-1){ bfs[one][two][three][four-1]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one,two),make_pair(three,four-1))); } if(four%6>1&&a[four/6][four%6-1]=='s'&&a[four/6][four%6-2]=='.'&&bfs[one][two][three][four-2]==-1){ bfs[one][two][three][four-2]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one,two),make_pair(three,four-2))); } if(four%6<5&&a[four/6][four%6+1]=='.'&&bfs[one][two][three][four+1]==-1){ bfs[one][two][three][four+1]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one,two),make_pair(three,four+1))); } if(four%6<4&&a[four/6][four%6+1]=='s'&&a[four/6][four%6+2]=='.'&&bfs[one][two][three][four+2]==-1){ bfs[one][two][three][four+2]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one,two),make_pair(three,four+2))); } if(four/6>0&&a[four/6-1][four%6]=='.'&&bfs[one][two][three][four-6]==-1){ bfs[one][two][three][four-6]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one,two),make_pair(three,four-6))); } if(four/6>1&&a[four/6-1][four%6]=='s'&&a[four/6-2][four%6]=='.'&&bfs[one][two][three][four-12]==-1){ bfs[one][two][three][four-12]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one,two),make_pair(three,four-12))); } if(four/6<5&&a[four/6+1][four%6]=='.'&&bfs[one][two][three][four+6]==-1){ bfs[one][two][three][four+6]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one,two),make_pair(three,four+6))); } if(four/6<4&&a[four/6+1][four%6]=='s'&&a[four/6+2][four%6]=='.'&&bfs[one][two][three][four+12]==-1){ bfs[one][two][three][four+12]=bfs[one][two][three][four]+1; Q.push(make_pair(make_pair(one,two),make_pair(three,four+12))); } a[one/6][one%6]='.'; a[two/6][two%6]='.'; a[three/6][three%6]='.'; a[four/6][four%6]='.'; } int ret=99999999; int perm[]={0,1,6,7}; do{ ret=min(ret,bfs[perm[0]][perm[1]][perm[2]][perm[3]]); }while(next_permutation(perm,perm+4)); if(ret==99999999)return -1; return ret; } };
*1:SystemTestは一発で通りました。250点切ってます。
