僕はパチモンクリーチャーを定期的に解きたくなります。よくわからないけど。
その都度、別の解法を試していますが、遅くなる一方です。
最初の提出の時は強引なDPで通して、その次には強引なBFSで通しました。
で、今回Dijkstraとメモ化再帰で書いてみました。が、Dijkstraも強引な最適化をしないと通らずメモ化は通りませんでした。シビア。
その4タイプのソースがこちらになりまス
DP(1450B)
DPは初期条件とか気をつけないと大変なことになる。
#include <iostream> #include <cstdlib> #include <vector> using namespace std; struct P{ int x,y,cost; P(int a,int b,int c){x = a, y = b , cost = c;} P(){} }; #define INF (1<<25) #define rep(i,n) for(int i=0; i<n ;i++) int dist(P a,P b){ return abs(a.x-b.x) + abs(a.y-b.y); } int main(){ int w,h; while(cin >> w >> h , w) { vector<P> data[5]; P start , goal ; start.cost = 0 , goal.cost = 0; rep(i,h)rep(j,w){ char c; cin >> c; if(c != '.'){ if(c == 'S')start.x = j , start.y = i; else if(c == 'G')goal.x = j , goal.y = i; else {P t(j,i,0) ; data[c-'1'].push_back(t);} } } int ret = INF , num ; P dp[5][1000]; rep(lp,5){ // start rep(i,5)rep(j,1000){dp[i][j].cost = INF;} int so = (lp+1)%5; rep(i,data[so].size()){ dp[so][i] = data[so][i]; dp[so][i].cost = dist(data[so][i],start); } rep(Z,3){ // remain int z = (lp+Z+2)%5; int prev = (z+4)%5; rep(i,data[prev].size()){ // prev rep(j,data[z].size()){ //cur int cost = dp[prev][i].cost + dist(dp[prev][i],data[z][j]); if(dp[z][j].cost > cost){ dp[z][j] = data[z][j] , dp[z][j].cost = cost; } } } } rep(i,data[(lp+4)%5].size() ){ int kCost = dp[(lp+4)%5][i].cost + dist(dp[(lp+4)%5][i],goal); if( kCost < ret){ ret = kCost , num = lp+1; } } } if(ret == INF)cout << "NA" << endl; else cout << num << " " << ret << endl; } }
BFS(1620B)
とりあえず強引に枝狩りしつつBFSするとなぜか通る。
#include <iostream> #include <vector> #include <algorithm> #include <queue> #include <cmath> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) #define INF (1<<25) struct P{ int x,y; P(int a,int b){x = a , y = b;} P(){} }; struct NODE{ int x,y,cost,cur,id; NODE(P a,int c,int d,int b){ x = a.x , y = a.y , cost = c , cur = d , id = b; } }; bool operator<(const NODE &a,const NODE &b){ return a.cost > b.cost; } #define next(n) ((n+1)%5) int getCost(P a,P b){ return abs(a.x-b.x)+abs(a.y-b.y); } int main(){ int W,H; while(cin >> W >> H,W){ vector<P> pos[5]; P goal,start; rep(i,H)rep(j,W){ char c; cin >> c; if(c == 'S')start = P(j,i); else if(c == 'G')goal = P(j,i); else if(c != '.')pos[c-'1'].push_back(P(j,i)); } int ans = INF , choice = -1; rep(X,5){ queue<NODE> Q; Q.push(NODE(start,0,X,1023)); int memo[5][1024]; rep(i,5)rep(j,1024) memo[i][j] = INF; while(Q.size()){ NODE q = Q.front(); Q.pop(); if(q.cost > memo[q.cur][q.id] )continue; if(next(q.cur) == X){ int lastCost = q.cost+getCost(P(q.x,q.y),goal); if( lastCost < ans ){ ans = lastCost; choice = X; } continue; } rep(i,pos[next(q.cur)].size()){ NODE t = NODE(pos[next(q.cur)][i] , q.cost+getCost(P(q.x,q.y),pos[next(q.cur)][i]) , next(q.cur) , i); if( t.cost < memo[t.cur][t.id]){ memo[t.cur][t.id] = t.cost; Q.push(t); } } } } if(~choice)cout << choice+1 << " " << ans << endl; else cout << "NA" << endl; } }
ダイクストラ(1593B)
BFSよりなんでか遅い。追加する段階でチェックしてunordered_mapとか使ってやっと通った。(unordered_mapは本来使う必要がないのだが手抜き)
#include <iostream> #include <vector> #include <tr1/unordered_map> #include <queue> #include <cstdio> #include <algorithm> using namespace std; int X,Y; struct NODE{ int x,y,z,cost,fc; NODE(int x,int y,int z,int cost,int fc): x(x) , y(y) , z(z) , cost(cost) , fc(fc) {} }; bool operator < (const NODE &a,const NODE &b){ return a.cost != b.cost ? a.cost > b.cost : a.fc > b.fc; } int x[5][1000]; int y[5][1000]; int sz[5]; int main(){ while(cin >> X >> Y && X){ int sx,sy,gx,gy; for(int i = 0 ; i < 5 ; i++) sz[i]=0; for(int i = 0 ; i < Y ; i++) for(int j = 0 ; j < X ; j++){ char c; scanf(" %c",&c); if(c == 'S'){ sx = j , sy = i; }else if( c == 'G'){ gx = j , gy = i; }else if( c != '.'){ c = c - '1'; x[c][sz[c]] = j; y[c][sz[c]++] = i; } } priority_queue<NODE> Q; for(int i = 0 ; i < 5 ; i++){ Q.push(NODE(sx,sy,(i+1)%5,0,i)); } tr1::unordered_map< int , int > memo[5][5]; while(Q.size()){ NODE q = Q.top(); Q.pop(); if(q.z == 10){ cout << q.fc+1 << " " << q.cost << endl; goto exit; } if(memo[q.z][q.fc][(q.x<<12)|q.y] < q.cost) continue; if(q.z == q.fc){ Q.push(NODE(gx,gy,10,q.cost+abs(q.x-gx)+abs(q.y-gy),q.fc)); }else{ for(int i = 0 ; i < sz[q.z] ; i++){ NODE t = NODE(x[q.z][i],y[q.z][i],(q.z+1)%5,q.cost+abs(q.x-x[q.z][i])+abs(q.y-y[q.z][i]),q.fc); if( !memo[t.z][t.fc].count((t.x<<12)|t.y) || t.cost < memo[t.z][t.fc][(t.x<<12)|t.y]) memo[t.z][t.fc][(t.x<<12)|t.y] = t.cost,Q.push(t); } } } cout << "NA" << endl; exit:; } }
メモ化再帰(1153B)
一番シンプルでそれなりに速かった。良かった。
#include <iostream> #include <vector> #include <cstring> #include <queue> #include <cstdio> #include <algorithm> using namespace std; #define INF (1<<25) int X,Y; int sx,sy,gx,gy; int x[5][1000]; int y[5][1000]; int memo[1000][5][5]; int sz[5]; int f(int w,int z,int s){ if((z+1)%5==s) return abs(x[z][w]-gx)+abs(y[z][w]-gy); if(~memo[w][z][s]) return memo[w][z][s]; int ans = INF; for(int i = 0 ; i < sz[(z+1)%5] ; i++){ ans = min(ans,f(i,(z+1)%5,s)+abs(x[z][w]-x[(z+1)%5][i])+abs(y[z][w]-y[(z+1)%5][i])); } return memo[w][z][s] = ans; } int main(){ while(cin >> X >> Y && X){ memset(memo,-1,sizeof(memo)); for(int i = 0 ; i < 5 ; i++) sz[i]=0; for(int i = 0 ; i < Y ; i++) for(int j = 0 ; j < X ; j++){ char c; scanf(" %c",&c); if(c == 'S'){ sx = j , sy = i; }else if( c == 'G'){ gx = j , gy = i; }else if( c != '.'){ c = c - '1'; x[c][sz[c]] = j; y[c][sz[c]++] = i; } } pair<int,int> ans(INF,-1); for(int i = 0 ; i < 5 ; i++){ for(int j = 0 ; j < sz[(i+1)%5] ; j++){ ans = min(ans,make_pair(abs(sx-x[(i+1)%5][j])+abs(sy-y[(i+1)%5][j])+f(j,(i+1)%5,i),i)); } } if(~ans.second)cout << ans.second+1 << " " << ans.first << endl; else cout << "NA" << endl; } }