いろいろなパチモンクリーチャー

僕はパチモンクリーチャーを定期的に解きたくなります。よくわからないけど。

その都度、別の解法を試していますが、遅くなる一方です。

最初の提出の時は強引なＤＰで通して、その次には強引なＢＦＳで通しました。

で、今回Dijkstraとメモ化再帰で書いてみました。が、Dijkstraも強引な最適化をしないと通らずメモ化は通りませんでした。シビア。

その４タイプのソースがこちらになりまス

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;
	}
		
}