AOJ 1281 : The Morning after Halloween
問題リンク：The Morning after Halloween | Aizu Online Judge
問題概要：
h*wのグリッドが与えられる
グリッドは壁と何もないマスからなり、その中に幽霊が１以上３以下存在する
幽霊はそれぞれ対応した目的地をもっており、すべての幽霊はその対応した目的地に移動したい
１ステップで隣接する上下左右に移動、または移動しない亊ができる
幽霊が動く際に、
・同じセルに２以上の幽霊がいること
・幽霊同士が移動する際に交差すること
は許されない
最小何ステップで目的を達成できるか
解法：
BFSで解いた
short mincost[16*16][16*16][16*16] という配列を用意する
これは各幽霊の状態の最小ステップ数を保存する
int だとMLEかも。。
後はpriority queueを使い上記の条件を満たす様にしながら最小ステップ数を求める
コード：
#include<iostream> #include<cstdio> #include<queue> #include<map> #include<set> #include<deque> #include<algorithm> #include<cassert> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) #define inf (1<<29) #define MAX 17 using namespace std; typedef pair<int,int> ii; int h,w,n; char G[MAX][MAX]; short ev[MAX*MAX][MAX*MAX]; short mincost[MAX*MAX][MAX*MAX][MAX*MAX]; int dx[] = {0,1,0,-1,0}; int dy[] = {1,0,-1,0,0}; int goal[3],sp[3]; char cc[3]; struct Pox { int cur[3]; short cost; Pox(int a=255,int b=255,int c=255,short cost=1000):cost(cost) { cur[0] = a, cur[1] = b, cur[2] = c; } bool operator < (const Pox &a)const { return cost > a.cost; } }; bool isValidMove(int p11,int p12,int p21,int p22) { if(p12 == p22)return false;//visited same point if(p12 == p21 && p11 == p22)return false;//cross return true; } bool fin_check(int *cur) { rep(i,n)if(cur[i] != goal[i])return false; return true; } void compute() { rep(i,MAX*MAX)rep(j,MAX*MAX)rep(k,MAX*MAX)mincost[i][j][k] = 1000; priority_queue<Pox> Q; mincost[sp[0]][sp[1]][sp[2]] = 1000; Q.push(Pox(sp[0],sp[1],sp[2],0)); while(!Q.empty()) { Pox pox = Q.top(); Q.pop(); if(fin_check(pox.cur)) { cout << (int)pox.cost << endl; return; } if(n == 1) { int x = pox.cur[0] % w; int y = pox.cur[0] / w; rep(i,5) { int nx = x + dx[i]; int ny = y + dy[i]; if(!( 0 <= nx && nx < w && 0 <= ny && ny < h ))continue; if(G[ny][nx] == '#')continue; if(mincost[nx+ny*w][0][0] > (pox.cost + 1)) { mincost[nx+ny*w][0][0] = pox.cost + 1; Pox next = Pox(nx+ny*w,0,0,pox.cost+1); Q.push(next); } } } else if(n == 2) { int x1 = pox.cur[0] % w; int y1 = pox.cur[0] / w; int x2 = pox.cur[1] % w; int y2 = pox.cur[1] / w; rep(i,5) { int nx1 = x1 + dx[i]; int ny1 = y1 + dy[i]; if(!( 0 <= nx1 && nx1 < w && 0 <= ny1 && ny1 < h ))continue; if(G[ny1][nx1] == '#')continue; rep(j,5) { int nx2 = x2 + dx[j]; int ny2 = y2 + dy[j]; if(!( 0 <= nx2 && nx2 < w && 0 <= ny2 && ny2 < h ))continue; if(G[ny2][nx2] == '#')continue; if(!isValidMove(pox.cur[0],nx1+ny1*w,pox.cur[1],nx2+ny2*w))continue; if(mincost[nx1+ny1*w][nx2+ny2*w][0] > (pox.cost + 1)) { mincost[nx1+ny1*w][nx2+ny2*w][0] = pox.cost + 1; Q.push(Pox(nx1+ny1*w,nx2+ny2*w,0,pox.cost+1)); } } } } else if(n == 3) { int x[3],y[3],nx[3],ny[3]; rep(i,3)x[i] = pox.cur[i] % w, y[i] = pox.cur[i] / w; rep(i,5) { nx[0] = x[0] + dx[i]; ny[0] = y[0] + dy[i]; if(!( 0 <= nx[0] && nx[0] < w && 0 <= ny[0] && ny[0] < h ))continue; if(G[ny[0]][nx[0]] == '#')continue; rep(j,5) { nx[1] = x[1] + dx[j]; ny[1] = y[1] + dy[j]; if(!( 0 <= nx[1] && nx[1] < w && 0 <= ny[1] && ny[1] < h ))continue; if(G[ny[1]][nx[1]] == '#')continue; if(!isValidMove(pox.cur[0],nx[0]+ny[0]*w,pox.cur[1],nx[1]+ny[1]*w))continue; rep(k,5) { nx[2] = x[2] + dx[k]; ny[2] = y[2] + dy[k]; if(!( 0 <= nx[2] && nx[2] < w && 0 <= ny[2] && ny[2] < h ))continue; if(G[ny[2]][nx[2]] == '#')continue; if(!isValidMove(pox.cur[0],nx[0]+ny[0]*w,pox.cur[2],nx[2]+ny[2]*w))continue; if(!isValidMove(pox.cur[1],nx[1]+ny[1]*w,pox.cur[2],nx[2]+ny[2]*w))continue; if(mincost[nx[0]+ny[0]*w][nx[1]+ny[1]*w][nx[2]+ny[2]*w] > (pox.cost + 1)) { mincost[nx[0]+ny[0]*w][nx[1]+ny[1]*w][nx[2]+ny[2]*w] = pox.cost + 1; Q.push(Pox(nx[0]+ny[0]*w,nx[1]+ny[1]*w,nx[2]+ny[2]*w,pox.cost+1)); } } } } } } assert(false); } int main() { while(scanf("%d %d %d",&w,&h,&n),h|w|n) { rep(i,3)sp[i] = 0; int cd = 0; map<char,int> dex; rep(i,h) { getchar(); rep(j,w) { scanf("%c",&G[i][j]); dex[G[i][j]] = j + i * w; if('a' <= G[i][j] && G[i][j] <= 'z') { sp[cd] = j + i * w; cc[cd++] = G[i][j]; } } } assert(n == cd); rep(i,n)goal[i] = dex['A'+cc[i]-'a']; compute(); } return 0; }
ちなみに、
最初に書いたコード（MLEやらTLEやらおこす）を下に残します
両側探索とかいろいろした結果５００行超えてて今思えばやばかったので..
そもそもグラフ全体をハッシュ化して持ち歩いたのがいけなかった
コード:
#include<iostream> #include<cstdio> #include<queue> #include<vector> #include<algorithm> #include<cmath> #include<cassert> #include<iomanip> #include<ctime> #include<deque> #include<cstdlib> #include<map> #include<set> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) #define inf (1<<29) #define MAX 17 using namespace std; typedef unsigned long long ull; typedef pair<int,int> ii; int dx[] = {+0,+1,+0,-1,0}; int dy[] = {+1,+0,-1,+0,0}; struct P { int p[3],cost; char c[3]; P(int cost=inf):cost(cost){ p[0] = p[1] = p[2] = inf; } bool operator < (const P& a)const { return cost > a.cost; } }; map<ull,int> mincostR,mincost; int w,h,n; char G[MAX][MAX],cc[3]; char initialD[MAX][MAX]; ull hash[MAX][MAX],tmp[MAX][MAX]; int ev[MAX*MAX][MAX*MAX];//A*用評価値 int pp[3],dex=0; int goal[3]; ull getHash(char a[MAX][MAX]) { const ull B1 = 9973; const ull B2 = 1000000007; ull t1 = 1; rep(i,w)t1 *= B1; rep(i,h) { ull e = 0; rep(j,w)e = e * B1 + a[i][j]; for(int j=0;j+w<=w;j++) { tmp[i][j] = e; if(j+w<w)e = e * B1 - t1 * a[i][j] + a[i][j+w]; } } ull t2 = 1; rep(i,h)t2 *= B2; for(int j=0;j+w<=w;j++) { ull e = 0; rep(i,w) e = e * B2 + tmp[i][j]; for(int i=0;i+h<=h;i++) { hash[i][j] = e; if(i+h<h)e = e * B2 - t2 * tmp[i][j] + tmp[i+h][j]; } } return hash[0][0]; } bool isValidMove(int p11,int p12,int p21,int p22) { if(p12 == p22)return false;//visited same point if(p12 == p21 && p11 == p22)return false;//cross return true; } void print(char a[MAX][MAX]) { rep(i,h) { rep(j,w) { cout << a[i][j]; } cout << endl; } cout << endl; } void preComputing(int depth) { mincostR.clear(); //char initialD[MAX][MAX]; //int pp[n],dex=0,cc[n]; dex = 0; rep(i,h)rep(j,w) { initialD[i][j] = G[i][j]; if('A' <= initialD[i][j] && initialD[i][j] <= 'Z')initialD[i][j] = (char)('a'+initialD[i][j]-'A'); else if('a' <= initialD[i][j] && initialD[i][j] <= 'z')initialD[i][j] = ' '; if('a' <= initialD[i][j] && initialD[i][j] <= 'z') { pp[dex] = i * w + j,cc[dex] = initialD[i][j]; //cout << "pre pp[" << dex << "] = " << pp[dex] % w << "," << pp[dex] / w << endl; //cout << "pre cc[" << dex << "] = " << cc[dex] << endl; dex++; } } assert(dex == n); mincostR[getHash(initialD)] = 0; rep(i,n) { int x = pp[i] % w; int y = pp[i] / w; initialD[y][x] = (char)('A'+initialD[y][x]-'a'); } priority_queue<P> Q; { P prep = P(0); rep(i,dex)prep.p[i] = pp[i],prep.c[i] = cc[i]; Q.push(prep); } while(!Q.empty()) { P p = Q.top(); Q.pop(); //cout << p.cost << " >= " << depth << endl; if(p.cost >= depth)return; /* char store[n]; int x[n],y[n]; rep(i,n)x[i] = p.p[i] % w,y[i] = p.p[i] / w; rep(i,n)store[i] = initialD[y[i]][x[i]]; rep(i,n)initialD[y[i]][x[i]] = p.c[i]; cout << "cost : " << p.cost << endl; print(initialD); rep(i,n)initialD[y[i]][x[i]] = store[i]; */ if(n == 1) { int x = p.p[0] % w; int y = p.p[0] / w; char c = p.c[0]; rep(i,5) { int nx = x + dx[i]; int ny = y + dy[i]; if(!( 0 <= nx && nx < w && 0 <= ny && ny < h ))continue; if(G[ny][nx] == '#')continue; char store = initialD[ny][nx]; initialD[ny][nx] = c; ull hsh = getHash(initialD); initialD[ny][nx] = store; if(mincostR.find(hsh) == mincostR.end()) { mincostR[hsh] = p.cost + 1; P next = P(p.cost+1); next.p[0] = nx + ny * w; next.c[0] = c; Q.push(next); } } } else if(n == 2) { assert(p.p[0] != inf && p.p[1] != inf); int x1 = p.p[0] % w; int y1 = p.p[0] / w; int x2 = p.p[1] % w; int y2 = p.p[1] / w; assert(G[y1][x1] != '#' && G[y2][x2] != '#'); rep(i,5) { int nx1 = x1 + dx[i]; int ny1 = y1 + dy[i]; if(!( 0 <= nx1 && nx1 < w && 0 <= ny1 && ny1 < h ))continue; if(G[ny1][nx1] == '#')continue; rep(j,5) { int nx2 = x2 + dx[j]; int ny2 = y2 + dy[j]; if(!( 0 <= nx2 && nx2 < w && 0 <= ny2 && ny2 < h ))continue; if(G[ny2][nx2] == '#')continue; if(!isValidMove(p.p[0],nx1+ny1*w,p.p[1],nx2+ny2*w))continue; char store1 = initialD[ny1][nx1],store2 = initialD[ny2][nx2]; initialD[ny1][nx1] = p.c[0]; initialD[ny2][nx2] = p.c[1]; //cout << "go next : " << endl; //print(initialD); //cout << "}}}}}}}}}}}}" << endl; ull hsh = getHash(initialD); initialD[ny1][nx1] = store1; initialD[ny2][nx2] = store2; if(mincostR.find(hsh) == mincostR.end()) { //cout << "yes,go next\n"; mincostR[hsh] = p.cost + 1; P next = P(p.cost+1); next.p[0] = nx1 + ny1 * w; next.p[1] = nx2 + ny2 * w; rep(k,2)next.c[k] = p.c[k];//MUDA Q.push(next); } //else cout << "no continue" << endl; } } } else if(n == 3) { int x[3],y[3],nx[3],ny[3]; rep(i,3)x[i] = p.p[i] % w, y[i] = p.p[i] / w; rep(i,5) { nx[0] = x[0] + dx[i]; ny[0] = y[0] + dy[i]; if(!( 0 <= nx[0] && nx[0] < w && 0 <= ny[0] && ny[0] < h ))continue; if(G[ny[0]][nx[0]] == '#')continue; rep(j,5) { nx[1] = x[1] + dx[j]; ny[1] = y[1] + dy[j]; if(!( 0 <= nx[1] && nx[1] < w && 0 <= ny[1] && ny[1] < h ))continue; if(G[ny[1]][nx[1]] == '#')continue; if(!isValidMove(p.p[0],nx[0]+ny[0]*w,p.p[1],nx[1]+ny[1]*w))continue; rep(k,5) { nx[2] = x[2] + dx[k]; ny[2] = y[2] + dy[k]; if(!( 0 <= nx[2] && nx[2] < w && 0 <= ny[2] && ny[2] < h ))continue; if(G[ny[2]][nx[2]] == '#')continue; if(!isValidMove(p.p[0],nx[0]+ny[0]*w,p.p[2],nx[2]+ny[2]*w))continue; if(!isValidMove(p.p[1],nx[1]+ny[1]*w,p.p[2],nx[2]+ny[2]*w))continue; char store[3]; rep(l,3)store[l] = initialD[ny[l]][nx[l]]; rep(l,3)initialD[ny[l]][nx[l]] = p.c[l]; ull hsh = getHash(initialD); rep(l,3)initialD[ny[l]][nx[l]] = store[l]; if(mincostR.find(hsh) == mincostR.end()) { mincostR[hsh] = p.cost + 1; P next = P(p.cost + 1); rep(l,3)next.p[l] = nx[l] + ny[l] * w,next.c[l] = p.c[l]; Q.push(next); } } } } } } } void makeEv() { rep(y,MAX*MAX)rep(x,MAX*MAX)ev[y][x] = inf; /* rep(y,h)rep(x,w) { deque<ii> deq; deq.push_back(ii(x+y*w,0)); ev[y*w+x][y*w+x] = 0; //cout << "cur ( " << x << "," << y << ")\n"; while(!deq.empty()) { ii state = deq.front(); deq.pop_front(); int cx = state.first % w; int cy = state.first / w; //cout << "state(" << state.first%w << "," << state.first/w << " : " << state.second << ")\n"; rep(j,4) { int nx = cx + dx[j]; int ny = cy + dy[j]; if(!(0 <= nx && nx < w && 0 <= ny && ny < h))continue; if(G[ny][nx] == '#')continue; if(ev[cy*w+cx][ny*w+nx] > state.second + 1) { ev[cy*w+cx][ny*w+nx] = state.second + 1; deq.push_back(ii(nx+ny*w,state.second+1)); } } } } */ //int x = 1,y = 3; rep(y,h)rep(x,w) { deque<ii> deq; deq.push_back(ii(x+y*w,0)); ev[x+y*w][x+y*w] = 0; while(!deq.empty()) { ii state = deq.front(); deq.pop_front(); int cx = state.first % w; int cy = state.first / w; rep(i,4) { int nx = cx + dx[i]; int ny = cy + dy[i]; if(!(0 <= nx && nx < w && 0 <= ny && ny < h))continue; if(G[ny][nx] == '#')continue; if(ev[x+y*w][nx+ny*w] > state.second + 1) { ev[x+y*w][nx+ny*w] = state.second + 1; deq.push_back(ii(nx+ny*w,state.second+1)); } } } } } void compute() { mincost.clear(); dex = 0; rep(y,h)rep(x,w) if('a' <= G[y][x] && G[y][x] <= 'z') pp[dex] = x + y * w,cc[dex++] = G[y][x]; rep(i,n) { char c = cc[i]; c = (char)('A'+c-'a'); map<char,int> index; rep(y,h)rep(x,w)index[G[y][x]] = y * w + x; goal[i] = index[c]; //cout << "pp = " << pp[i]%w << "," << pp[i]/w << endl; //cout << cc[i] << " c = " << c << endl; //cout << "goal[" << i << "] = " << goal[i] % w << "," << goal[i] / w << endl; } priority_queue<P> Q; { P prep = P(0); rep(i,dex)prep.p[i] = pp[i],prep.c[i] = cc[i]; Q.push(prep); } int ans = inf; while(!Q.empty()) { P p = Q.top(); Q.pop(); if(p.cost >= ans)continue; int add_cost = 0; rep(i,n) { add_cost = max(add_cost,ev[p.p[i]][goal[i]]); //cout << "e["<<p.p[i]%w << "," <<p.p[i]/w<<"]["<<goal[i]%w << "," << goal[i]/w<<"] = " << ev[p.p[i]][goal[i]] << endl; } //cout << p.cost << " + " << add_cost << " >= " << ans << endl; if(p.cost+add_cost >= ans)continue; /* char store[n]; int x[n],y[n]; rep(i,n)x[i] = p.p[i] % w,y[i] = p.p[i] / w; rep(i,n)store[i] = initialD[y[i]][x[i]]; rep(i,n)initialD[y[i]][x[i]] = p.c[i]; cout << "cost : " << p.cost << endl; print(initialD); rep(i,n)initialD[y[i]][x[i]] = store[i]; */ if(n == 1) { int x = p.p[0] % w; int y = p.p[0] / w; char c = p.c[0]; rep(i,5) { int nx = x + dx[i]; int ny = y + dy[i]; if(!( 0 <= nx && nx < w && 0 <= ny && ny < h ))continue; if(G[ny][nx] == '#')continue; char store = initialD[ny][nx]; initialD[ny][nx] = c; ull hsh = getHash(initialD); initialD[ny][nx] = store; if(mincost.find(hsh) == mincost.end()) { mincost[hsh] = p.cost + 1; if(mincostR.find(hsh) != mincostR.end()) { ans = min(ans,p.cost+1+mincostR[hsh]); continue; } P next = P(p.cost+1); next.p[0] = nx + ny * w; next.c[0] = c; Q.push(next); } } } else if(n == 2) { assert(p.p[0] != inf && p.p[1] != inf); int x1 = p.p[0] % w; int y1 = p.p[0] / w; int x2 = p.p[1] % w; int y2 = p.p[1] / w; assert(G[y1][x1] != '#' && G[y2][x2] != '#'); rep(i,5) { int nx1 = x1 + dx[i]; int ny1 = y1 + dy[i]; if(!( 0 <= nx1 && nx1 < w && 0 <= ny1 && ny1 < h ))continue; if(G[ny1][nx1] == '#')continue; rep(j,5) { int nx2 = x2 + dx[j]; int ny2 = y2 + dy[j]; if(!( 0 <= nx2 && nx2 < w && 0 <= ny2 && ny2 < h ))continue; if(G[ny2][nx2] == '#')continue; if(!isValidMove(p.p[0],nx1+ny1*w,p.p[1],nx2+ny2*w))continue; char store1 = initialD[ny1][nx1],store2 = initialD[ny2][nx2]; initialD[ny1][nx1] = p.c[0]; initialD[ny2][nx2] = p.c[1]; ull hsh = getHash(initialD); initialD[ny1][nx1] = store1; initialD[ny2][nx2] = store2; if(mincost.find(hsh) == mincost.end()) { mincost[hsh] = p.cost + 1; if(mincostR.find(hsh) != mincostR.end()) { ans = min(ans,p.cost+1+mincostR[hsh]); continue; } P next = P(p.cost+1); next.p[0] = nx1 + ny1 * w; next.p[1] = nx2 + ny2 * w; rep(k,2)next.c[k] = p.c[k];//MUDA Q.push(next); } } } } else if(n == 3) { int x[3],y[3],nx[3],ny[3]; rep(i,3)x[i] = p.p[i] % w, y[i] = p.p[i] / w; rep(i,5) { nx[0] = x[0] + dx[i]; ny[0] = y[0] + dy[i]; if(!( 0 <= nx[0] && nx[0] < w && 0 <= ny[0] && ny[0] < h ))continue; if(G[ny[0]][nx[0]] == '#')continue; rep(j,5) { nx[1] = x[1] + dx[j]; ny[1] = y[1] + dy[j]; if(!( 0 <= nx[1] && nx[1] < w && 0 <= ny[1] && ny[1] < h ))continue; if(G[ny[1]][nx[1]] == '#')continue; if(!isValidMove(p.p[0],nx[0]+ny[0]*w,p.p[1],nx[1]+ny[1]*w))continue; rep(k,5) { nx[2] = x[2] + dx[k]; ny[2] = y[2] + dy[k]; if(!( 0 <= nx[2] && nx[2] < w && 0 <= ny[2] && ny[2] < h ))continue; if(G[ny[2]][nx[2]] == '#')continue; if(!isValidMove(p.p[0],nx[0]+ny[0]*w,p.p[2],nx[2]+ny[2]*w))continue; if(!isValidMove(p.p[1],nx[1]+ny[1]*w,p.p[2],nx[2]+ny[2]*w))continue; char store[3]; rep(l,3)store[l] = initialD[ny[l]][nx[l]]; rep(l,3)initialD[ny[l]][nx[l]] = p.c[l]; ull hsh = getHash(initialD); rep(l,3)initialD[ny[l]][nx[l]] = store[l]; if(mincost.find(hsh) == mincost.end()) { mincost[hsh] = p.cost + 1; if(mincostR.find(hsh) != mincostR.end()) { ans = min(ans,p.cost+1+mincostR[hsh]); continue; } P next = P(p.cost + 1); rep(l,3)next.p[l] = nx[l] + ny[l] * w,next.c[l] = p.c[l]; Q.push(next); } } } } } } printf("%d\n",ans); //cout << ans << endl; } int main() { //clock_t st,ed; //st = clock(); while(scanf("%d %d %d",&w,&h,&n),w|h|n) { rep(i,h) { getchar(); rep(j,w) scanf("%c",&G[i][j]); } preComputing(25);//大きくするとMLE、小さくするとTLE makeEv(); compute(); } //ed = clock(); //cout << setiosflags(ios::fixed) << setprecision(10) << "time : " << (double)(ed-st)/CLOCKS_PER_SEC << endl; return 0; }
