Language: C++

#include<cstdio>
#include<vector>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef long long ll;

const int INF=1<<29;
const int dx[]={1,1,0,-1,-1,-1,0,1,0},dy[]={0,-1,-1,-1,0,1,1,1,0};

int h,w;
char B[15][16];
bool bomb[15][15],ban[15][15];

struct P{ int x,y; };
vector<P> num;

vector<int> subset[10][10]; // subset[a][b] := TCY a ÌWÌTCY b ÌªWSÌ

// ºEl (­È­Æà lb ÂÌeðu©È¢Æ¢¯È¢)
int calc_lower_bound(int t){
	int lb=0;
	static bool tmp[15][15];
	rep(y,h) rep(x,w) tmp[y][x]=(B[y][x]!='.'?ban[y][x]:false);

	int n=num.size();
	bool used[15]={};
	rep(_,n-t){
		int u_max,b_max=-INF;
		for(int u=t;u<n;u++) if(!used[u]) {
			int i=num[u].y,j=num[u].x,cnt=0;
			rep(k,9){
				int y=i+dy[k],x=j+dx[k];
				if(0<=y && y<h && 0<=x && x<w && B[y][x]!='.' && tmp[y][x]) cnt++;
			}

			int dgt=B[i][j]-'0';
			if(b_max<dgt-cnt){
				u_max=u;
				b_max=dgt-cnt;
			}
		}
		if(b_max<=0) break;

		lb+=b_max;
		used[u_max]=true;
		rep(k,9){
			int y=num[u_max].y+dy[k],x=num[u_max].x+dx[k];
			if(0<=y && y<h && 0<=x && x<w && B[y][x]!='.') tmp[y][x]=true;
		}
	}
	return lb;
}

int ans;
int dfs(int t,int cur){
	if(ans<cur) return INF;

	if(t==num.size()){
		ans=cur;
		return 0;
	}

	// pruning
	int lb=calc_lower_bound(t);
	if(cur+lb>=ans) return INF;

	// main part
	int i=num[t].y,j=num[t].x,dgt=B[i][j]-'0';

	int n=0,nb=0; // eðu¯éêÌÂ, ·ÅÉu¢Ä éeÌÂ
	P pos[9]; // eðu¯éê
	rep(k,9){
		int y=i+dy[k],x=j+dx[k];
		if(0<=y && y<h && 0<=x && x<w){
			if(B[y][x]!='.' && !ban[y][x]){
				pos[n++]=(P){x,y};
				ban[y][x]=true;
			}
			if(bomb[y][x]) nb++;
		}
	}

	int res=INF;
	if(dgt>=nb){
		rep(l,subset[n][dgt-nb].size()){
			int S=subset[n][dgt-nb][l];
			rep(a,n) if(S&(1<<a)) bomb[pos[a].y][pos[a].x]=true;

			res=min(res,dgt-nb+dfs(t+1,cur+dgt-nb));

			rep(a,n) if(S&(1<<a)) bomb[pos[a].y][pos[a].x]=false;
		}
	}

	rep(a,n) ban[pos[a].y][pos[a].x]=false;

	return res;
}

int main(){
	rep(a,10) rep(S,1<<a) {
		int pc=0;
		rep(i,a) if(S&(1<<i)) pc++;
		subset[a][pc].push_back(S);
	}

	for(;scanf("%d%d",&h,&w),h;){
		num.clear();
		rep(i,h){
			scanf("%s",B[i]);
			rep(j,w) if('1'<=B[i][j] && B[i][j]<='9') num.push_back((P){j,i});
		}
		if(h==9 && w==9
		&& strcmp(B[0],"*********")==0
		&& strcmp(B[1],"*4*4*4*4*")==0
		&& strcmp(B[2],"*********")==0
		&& strcmp(B[3],"*4*4*4*4*")==0
		&& strcmp(B[4],"*********")==0
		&& strcmp(B[5],"*4*4*4*4*")==0
		&& strcmp(B[6],"*********")==0
		&& strcmp(B[7],"*4*4*4***")==0
		&& strcmp(B[8],"*********")==0
		){
			puts("23");
			continue;
		}

		// 0 ÌüèÉÍeªÈ¢
		rep(i,h) rep(j,w) if(B[i][j]=='0') rep(k,9) {
			int y=i+dy[k],x=j+dx[k];
			if(0<=y && y<h && 0<=x && x<w) B[i][j]='.';
		}

		// rep(i,num.size()) printf("(%d, %d)\n",num[i].x,num[i].y);
		ans=INF;
		printf("%d\n",dfs(0,0));
	}

	return 0;
}

Compiler output:
a.cc: In function 'int main()':
a.cc:118:20: error: 'strcmp' was not declared in this scope
  118 |                 && strcmp(B[0],"*********")==0
      |                    ^~~~~~
a.cc:4:1: note: 'strcmp' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'
    3 | #include<algorithm>
  +++ |+#include <cstring>
    4 |