1245-Gap

問題概要

(後で書く)

解法

最良優先探索．
出来るだけ多くのものが正しい位置に定まっているものから探索する．

実装(C++)

いろいろと嘘解法

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <iostream>
using namespace std;

typedef long long int lli;

#define REP(i,x) for(int i=0;i<(int)(x);i++)

uint mod_pow(uint a,uint n,uint M){
	if(n==0)return 1;
	uint res=mod_pow(a*a%M,n>>1,M);
	if(n&1)res=(res*a)%M;
	return res;
}
int PRIME[8][4]={
		{419,421,431,433},
		{479,487,491,499},
		{2377,2381,2383,2389},
		{2417,2423,2437,2441},
		{839,853,857,859},
		{229,233,239,241},
		{181,191,193,197},
		{101,103,107,109}
};
const int MOD=1000000009;

struct State{
	short TABLE[8][4];
	int hash;
	int eq;
	State(){
		memset(TABLE,0,8*4*sizeof(short));
		hash=0;eq=0;
	}
	void put(int x,int y,int v){
		TABLE[x][y]=v;
		if(x+1+(y+1)*10==v)eq++;
		hash=(hash+mod_pow(PRIME[x][y],v,MOD))%MOD;
	}
	void remove(int x,int y){
		hash=((long long)hash+MOD-mod_pow(PRIME[x][y],TABLE[x][y],MOD))%MOD;
		if(TABLE[x][y]==(x+1)+(y+1)*10)eq--;
		TABLE[x][y]=0;
	}
};
bool operator<(const State &a,const State &b){
	return a.eq<b.eq;
}
int ans=99999999;
void solve(State init){
	ans=99999999;
	map<int,int> ac;
	ac[init.hash]=0;
	priority_queue<State> que;
	que.push(init);
	while(!que.empty()){
		init=que.top();que.pop();
		int now=ac[init.hash];
		if(init.eq==28){
			ans=now;
			continue;
		}
		if(ans<=now+28-init.eq)continue;
		//0を検索する
		for(int x=1;x<8;x++){
			for(int y=0;y<4;y++){
				if(init.TABLE[x][y]==0){
					int tx=x-1;
					//while(init.TABLE[tx][y]==0)tx--;
					if(init.TABLE[tx][y]%10==7)continue;
					if(init.TABLE[tx][y]==0)continue;
					State next=init;
					int nv=init.TABLE[tx][y]+1;
					for(int nx=1;nx<8;nx++){
						for(int ny=0;ny<4;ny++){
							if(next.TABLE[nx][ny]==nv){
								next.remove(nx,ny);
							}
						}
					}
					next.put(x,y,nv);
					if(ac.find(next.hash)==ac.end()||ac[next.hash]>now+1){
						ac[next.hash]=now+1;
						que.push(next);
					}
				}
			}
		}
	}

	if(ans==99999999){
		cout<<-1<<endl;
	}else{
		cout<<ans<<endl;
	}
}
int main(){
	int T;
	cin>>T;
	REP(i,T){
		State init;
		REP(y,4){
			REP(x,7){
				int t;
				cin>>t;
				init.put(x+1,y,t);
			}
		}

		REP(y,4)for(int x=1;x<8;x++){
			if(init.TABLE[x][y]%10==1){
				int v=init.TABLE[x][y];
				init.put(0,v/10-1,v);
				init.remove(x,y);
			}
		}
		solve(init);

	}
	return 0;
}