Language: C++

#include<iostream>
#include<algorithm>
#include<map>
#include<cassert>

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

#define MAX 15
#define INF (1<<29)
static const int di[9] = {0, 0, -1, -1, -1, 0, 1, 1, 1};
static const int dj[9] = {0, 1, 1, 0, -1, -1, -1, 0, 1};
long long T[17];
int size;

class State{
public:
  int pos, sum;
  long long val;
  State(){ sum = pos = val = 0;}
  bool operator < ( const State &s) const{
    if ( pos != s.pos ) return pos < s.pos;
    return val < s.val;
  }

  int getValue(int i){
    return (val%(T[i+1]))/T[i];
  }
  void setValue(int i, int x){
    val -= getValue(i)*T[i];
    val += x*T[i];
  }
  void inc(int i, int f){
    val += f*T[i];
  }
};

int H, W, dsize;
char M[MAX][MAX]; //map
int I[MAX][MAX]; // index of number P
pair<int, int> D[9*MAX]; // * for depth
pair<int, int> PI[MAX]; // * for depth
map<State, int> memo;

bool isout(int ni, int nj){
  if (ni < 0 || nj < 0 || H <= ni || W <= nj) return true;
  return I[ni][nj] == -1;
}

int dfs(State &u){
  //  cout << memo.size() << endl;
  if ( u.sum == 0 ) return memo[u] = 0;
  if ( memo.count(u) ) return  memo[u];
  if ( u.pos >= dsize ) return memo[u] = INF;

  rep(i, size){
    if ( PI[i].first + 1 < D[u.pos].first && u.getValue(i) > 0 ) return memo[u] = INF;
  }

  if ( u.sum/2 > dsize-u.pos ) return memo[u] = INF; !!!! uso edagari

  int res;

  u.pos++;
  res = dfs(u);
  u.pos--;

  if ( u.sum == 0 ) return memo[u] = res;

  rep(r, 9){
    int ni = D[u.pos].first + di[r];
    int nj = D[u.pos].second + dj[r];
    if ( isout(ni, nj) ) continue;
    if ( u.getValue(I[ni][nj]) == 0 ) return memo[u] = res;
  }

  rep(r, 9){
    int ni = D[u.pos].first + di[r];
    int nj = D[u.pos].second + dj[r];
    if ( isout(ni, nj) ) continue;
    u.inc(I[ni][nj], -1);
    u.sum--;
  }

  u.pos++;
  res = min(res, dfs(u) + 1);
  u.pos--;

  rep(r, 9){
    int ni = D[u.pos].first + di[r];
    int nj = D[u.pos].second + dj[r];
    if ( isout(ni, nj) ) continue;
    u.inc(I[ni][nj], 1);
    u.sum++;
  }

  return memo[u] = res;
}

main(){
  long long p = 1;
  rep(i, 17) { T[i] = p; p *= 10;};

  while(1){
    cin >> H >> W;
    if ( H == 0 && W == 0 ) break;
    State init;
    size = dsize = 0;
    rep(i, H) rep(j, W) I[i][j] = -1;
    
    memo.clear();
    
    rep(i, H) rep(j, W){
      cin >> M[i][j];
      if ( isdigit(M[i][j]) ){
	I[i][j] = size;
	PI[size] = make_pair(i, j);
	init.setValue(size++, (M[i][j]-'0'));
	init.sum += (M[i][j]-'0');
      }
    }
    rep(i, H) rep(j, W){
      if  ( M[i][j] == '*' || isdigit(M[i][j]) ){
	bool target = false;
	rep(r, 9){
	  int ni = i + di[r];
	  int nj = j + dj[r];
	  if ( 0 <= ni  && 0 <= nj && ni < H && nj < W ){
	    if ( '0' <= M[ni][nj]  && M[ni][nj] <= '9' ) { target = true; break;}
	  }
	}
	if ( target )  D[dsize++] = make_pair(i, j);
      }
    }

    cout << dfs(init) << endl;
  }
}

Compiler output:
a.cc: In function 'int dfs(State&)':
a.cc:56:10: error: reference to 'size' is ambiguous
   56 |   rep(i, size){
      |          ^~~~
a.cc:7:39: note: in definition of macro 'rep'
    7 | #define rep(i,n) for ( int i = 0; i < n; i++)
      |                                       ^
In file included from /usr/include/c++/14/string:53,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:1:
/usr/include/c++/14/bits/range_access.h:272:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  272 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:262:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  262 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
a.cc:14:5: note:                 'int size'
   14 | int size;
      |     ^~~~
a.cc:60:59: error: 'uso' was not declared in this scope
   60 |   if ( u.sum/2 > dsize-u.pos ) return memo[u] = INF; !!!! uso edagari
      |                                                           ^~~
a.cc:65:3: error: 'res' was not declared in this scope; did you mean 'rep'?
   65 |   res = dfs(u);
      |   ^~~
      |   rep
a.cc: At global scope:
a.cc:100:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  100 | main(){
      | ^~~~
a.cc: In function 'int main()':
a.cc:108:5: error: reference to 'size' is ambiguous
  108 |     size = dsize = 0;
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:272:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  272 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:262:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  262 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
a.cc:14:5: note:                 'int size'
   14 | int size;
      |     ^~~~
a.cc:116:19: error: reference to 'size' is ambiguous
  116 |         I[i][j] = size;
      |                   ^~~~
/usr/include/c++/14/bits/range_access.h:272:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  272 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:262:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  262 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
a.cc:14:5: note:                 'int size'
   14 | int size;
      |     ^~~~
a.cc:117:12: error: reference to 'size' is ambiguous
  117 |         PI[size] = make_pair(i, j);
      |            ^~~~
/usr/include/c++/14/bits/range_access.h:272:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  272 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:262:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  262 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
a.cc:14:5: note:                 'int size'
   14 | int size;
      |     ^~~~
a.cc:118:23: error: reference to 'size' is ambiguous
  118 |         init.setValue(size++, (M[i][j]-'0'));
      |                       ^~~~
/usr/include/c++/14/bits/range_access.h:272:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  272 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:262:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  262 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
a.cc:14:5: note:                 'int size'
   14 | int size;
      |     ^~~~