AOJ 1321: Captain Q's Treasure

これは
ブログに記事を書きます Advent Calendar 2014 - Adventar
の4日目

幾度となく汚い言葉を発しながらも何とか書き上げて通すことができました。
何とかして上手くデータもって気合で枝を刈るだけ。

#include<stdio.h>
#include<algorithm>
#include<map>
using namespace std;
char str[17][17];
int dx[]={-1,-1,-1,0,0,0,1,1,1};
int dy[]={-1,0,1,-1,0,1,-1,0,1};
int v[17][17];
int u[17][17];
int row[310];
int col[310];
int sz;
int n,m;
struct wolf{
	long long t;
	int s;
	wolf(){t=0;s=0;}
};
inline bool operator<(const wolf&a,const wolf&b){
	if(a.t!=b.t)return a.t<b.t;
	return a.s<b.s;
}
long long pow10[19];
inline int ABS(int a){return max(a,-a);}
int ret=99999999;
int id;
int ir[20];
int ic[20];
map<wolf,int>dp;
int solve(int a,wolf b){
	if(dp.count(b))return dp[b];
//	printf("%d %lld %d\n",a,b.t,c);
	bool dame=false;
	for(int i=0;i<id;i++){
		int cnt=0;
		for(int j=a;j<sz;j++){
			if(ABS(ir[i]-row[j])<=1&&ABS(ic[i]-col[j])<=1)cnt++;
		}
		if(cnt<b.t%pow10[i+1]/pow10[i]){dame=true;break;}
	}
	if(dame){
		return dp[b]=99999999;
	}
	if(a==sz){
		return dp[b]=0;
	}
	int ret=99999999;
	
	b.s++;
	bool ok=true;
	for(int i=0;i<id;i++){
		if(ABS(ir[i]-row[a])<=1&&ABS(ic[i]-col[a])<=1&&b.t%pow10[i+1]/pow10[i]==0)ok=false;
	}
	//printf("%d %lld %d %d\n",a,b.t,ok,c);
	if(ok){
		for(int i=0;i<id;i++){
			if(ABS(ir[i]-row[a])<=1&&ABS(ic[i]-col[a])<=1)b.t-=pow10[i];
		}
		ret=min(ret,solve(a+1,b)+1);
		for(int i=0;i<id;i++){
			if(ABS(ir[i]-row[a])<=1&&ABS(ic[i]-col[a])<=1)b.t+=pow10[i];
		}	
	}
	ret=min(ret,solve(a+1,b));
	b.s--;
	return dp[b]=ret;
}
int main(){
	int a,b;
	pow10[0]=1;
	for(int i=1;i<19;i++)pow10[i]=pow10[i-1]*10;
	while(scanf("%d%d",&a,&b),a){
		n=a;m=b;
		id=0;
		sz=0;
		dp.clear();
		ret=99999999;
		wolf st;
		for(int i=0;i<a;i++)scanf("%s",str[i]);
		for(int i=0;i<a;i++)for(int j=0;j<b;j++)v[i][j]=u[i][j]=0;
		//for(int i=0;i<a;i++)for(int j=0;j<b;j++)if(str[i][j]=='.')v[i][j]=-1;
		for(int i=0;i<a;i++){
			for(int j=0;j<b;j++){
				if('0'<=str[i][j]&&str[i][j]<='9'){
					ir[id]=i;
					ic[id++]=j;
					st.t+=pow10[id-1]*(str[i][j]-'0');
					v[i][j]=str[i][j]-'0';
					for(int k=0;k<9;k++){
						if(0<=i+dx[k]&&i+dx[k]<a&&0<=j+dy[k]&&j+dy[k]<b&&str[i+dx[k]][j+dy[k]]!='.'){
							u[i+dx[k]][j+dy[k]]++;
						}
					}
				}
			}
		}
	//	for(int k=1;k<=9;k++)
		for(int i=0;i<a;i++)for(int j=0;j<b;j++)if(u[i][j]){
			row[sz]=i;col[sz++]=j;
		}
		printf("%d\n",solve(0,st));
	}
}