Language: C++

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cassert>
#include<iomanip>
#include<ctime>
#include<deque>
#include<cstdlib>
#include<map>
#include<set>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29)
#define MAX 17

using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> ii;

int dx[] = {+0,+1,+0,-1,0};
int dy[] = {+1,+0,-1,+0,0};

struct P
{
  int p[3],cost;
  char c[3];
  P(int cost=inf):cost(cost){ p[0] = p[1] = p[2] = inf; }
  bool operator < (const P& a)const
  {
    return cost > a.cost;
  }
};

map<ull,int> mincostR,mincost;
int w,h,n;
char G[MAX][MAX],cc[3];
char initialD[MAX][MAX];
ull hash[MAX][MAX],tmp[MAX][MAX];
int ev[MAX*MAX][MAX*MAX];//A*用評価値
int pp[3],dex=0;
int goal[3];

ull getHash(char a[MAX][MAX])
{
  const ull B1 = 9973;
  const ull B2 = 1000000007;

  ull t1 = 1;
  rep(i,w)t1 *= B1;

  rep(i,h)
    {
      ull e = 0;
      rep(j,w)e = e * B1 + a[i][j];

      for(int j=0;j+w<=w;j++)
	{
	  tmp[i][j] = e;
	  if(j+w<w)e = e * B1 - t1 * a[i][j] + a[i][j+w];
	}
    }

  ull t2 = 1;
  rep(i,h)t2 *= B2;

  for(int j=0;j+w<=w;j++)
    {
      ull e = 0;
      rep(i,w) e = e * B2 + tmp[i][j];

      for(int i=0;i+h<=h;i++)
	{
	  hash[i][j] = e;
	  if(i+h<h)e = e * B2 - t2 * tmp[i][j] + tmp[i+h][j];
	}
    }
  return hash[0][0];
}

bool isValidMove(int p11,int p12,int p21,int p22)
{
  if(p12 == p22)return false;//visited same point
  if(p12 == p21 && p11 == p22)return false;//cross

  return true;
}

void print(char a[MAX][MAX])
{
  rep(i,h)
    {
      rep(j,w)
	{
	  cout << a[i][j];
	}
      cout << endl;
    }
  cout << endl;
}

void preComputing(int depth)
{
  mincostR.clear();
  //char initialD[MAX][MAX];
  //int pp[n],dex=0,cc[n];
  dex = 0;
  rep(i,h)rep(j,w)
    {
      initialD[i][j] = G[i][j];
      if('A' <= initialD[i][j] && initialD[i][j] <= 'Z')initialD[i][j] = (char)('a'+initialD[i][j]-'A');
      else if('a' <= initialD[i][j] && initialD[i][j] <= 'z')initialD[i][j] = ' ';
      if('a' <= initialD[i][j] && initialD[i][j] <= 'z')
	{
	  pp[dex] = i * w + j,cc[dex] = initialD[i][j];
	  //cout << "pre pp[" << dex << "] = " << pp[dex] % w << "," << pp[dex] / w << endl;
	  //cout << "pre cc[" << dex << "] = " << cc[dex] << endl;
	  dex++;
	}
    }

  assert(dex == n);
  mincostR[getHash(initialD)] = 0;
  rep(i,n)
    {
      int x = pp[i] % w;
      int y = pp[i] / w;
      initialD[y][x] = (char)('A'+initialD[y][x]-'a');
    }

  priority_queue<P> Q;
  {
    P prep = P(0);
    rep(i,dex)prep.p[i] = pp[i],prep.c[i] = cc[i];
    Q.push(prep);
  }

  while(!Q.empty())
    {
      P p = Q.top(); Q.pop();
      //cout << p.cost << " >= " << depth << endl;
      if(p.cost >= depth)return;

      /*
      char store[n];
      int x[n],y[n];
      rep(i,n)x[i] = p.p[i] % w,y[i] = p.p[i] / w;
      rep(i,n)store[i] = initialD[y[i]][x[i]];
      rep(i,n)initialD[y[i]][x[i]] = p.c[i];
      cout << "cost : " << p.cost << endl;
      print(initialD);
      rep(i,n)initialD[y[i]][x[i]] = store[i];
      */

      if(n == 1)
	{
	  int x = p.p[0] % w;
	  int y = p.p[0] / w;
	  char c = p.c[0];
	  rep(i,5)
	    {
	      int nx = x + dx[i];
	      int ny = y + dy[i];
	      if(!( 0 <= nx && nx < w && 0 <= ny && ny < h ))continue;
	      if(G[ny][nx] == '#')continue;
	      
	      char store = initialD[ny][nx];
	      initialD[ny][nx] = c;
	      ull hsh = getHash(initialD);
	      initialD[ny][nx] = store;
	      if(mincostR.find(hsh) == mincostR.end())
		{
		  mincostR[hsh] = p.cost + 1;
		  P next = P(p.cost+1);
		  next.p[0] = nx + ny * w;
		  next.c[0] = c;
		  Q.push(next);
		}
	    }
	}
      else if(n == 2)
	{
	  assert(p.p[0] != inf && p.p[1] != inf);
	  int x1 = p.p[0] % w;
	  int y1 = p.p[0] / w;
	  int x2 = p.p[1] % w;
	  int y2 = p.p[1] / w;
	  assert(G[y1][x1] != '#' && G[y2][x2] != '#');

	  rep(i,5)
	    {
	      int nx1 = x1 + dx[i];
	      int ny1 = y1 + dy[i];
	      if(!( 0 <= nx1 && nx1 < w && 0 <= ny1 && ny1 < h ))continue;
	      if(G[ny1][nx1] == '#')continue;

	      rep(j,5)
		{
		  int nx2 = x2 + dx[j];
		  int ny2 = y2 + dy[j];
		  if(!( 0 <= nx2 && nx2 < w && 0 <= ny2 && ny2 < h ))continue;
		  if(G[ny2][nx2] == '#')continue;
		  if(!isValidMove(p.p[0],nx1+ny1*w,p.p[1],nx2+ny2*w))continue;

		  char store1 = initialD[ny1][nx1],store2 = initialD[ny2][nx2];
		  initialD[ny1][nx1] = p.c[0];
		  initialD[ny2][nx2] = p.c[1];
		  //cout << "go next : " << endl;
		  //print(initialD);
		  //cout << "}}}}}}}}}}}}" << endl;
		  ull hsh = getHash(initialD);
		  initialD[ny1][nx1] = store1;
		  initialD[ny2][nx2] = store2;

		  if(mincostR.find(hsh) == mincostR.end())
		    {
		      //cout << "yes,go next\n";
		      mincostR[hsh] = p.cost + 1;
		      P next = P(p.cost+1);
		      next.p[0] = nx1 + ny1 * w;
		      next.p[1] = nx2 + ny2 * w;
		      rep(k,2)next.c[k] = p.c[k];//MUDA
		      Q.push(next);
		    }
		  //else cout << "no continue" << endl;
		}
	    }
	}
      else if(n == 3)
	{

	  int x[3],y[3],nx[3],ny[3];
	  rep(i,3)x[i] = p.p[i] % w, y[i] = p.p[i] / w;

	  rep(i,5)
	    {
	      nx[0] = x[0] + dx[i];
	      ny[0] = y[0] + dy[i];
	      if(!( 0 <= nx[0] && nx[0] < w && 0 <= ny[0] && ny[0] < h ))continue;
	      if(G[ny[0]][nx[0]] == '#')continue;

	      rep(j,5)
		{
		  nx[1] = x[1] + dx[j];
		  ny[1] = y[1] + dy[j];
		  if(!( 0 <= nx[1] && nx[1] < w && 0 <= ny[1] && ny[1] < h ))continue;
		  if(G[ny[1]][nx[1]] == '#')continue;
		  if(!isValidMove(p.p[0],nx[0]+ny[0]*w,p.p[1],nx[1]+ny[1]*w))continue;

		  rep(k,5)
		    {
		      nx[2] = x[2] + dx[k];
		      ny[2] = y[2] + dy[k];
		      if(!( 0 <= nx[2] && nx[2] < w && 0 <= ny[2] && ny[2] < h ))continue;
		      if(G[ny[2]][nx[2]] == '#')continue;
		      if(!isValidMove(p.p[0],nx[0]+ny[0]*w,p.p[2],nx[2]+ny[2]*w))continue;
		      if(!isValidMove(p.p[1],nx[1]+ny[1]*w,p.p[2],nx[2]+ny[2]*w))continue;

		      char store[3];
		      rep(l,3)store[l] = initialD[ny[l]][nx[l]];
		      rep(l,3)initialD[ny[l]][nx[l]] = p.c[l];
		      ull hsh = getHash(initialD);
		      rep(l,3)initialD[ny[l]][nx[l]] = store[l];
		      if(mincostR.find(hsh) == mincostR.end())
			{
			  mincostR[hsh] = p.cost + 1;
			  P next = P(p.cost + 1);
			  rep(l,3)next.p[l] = nx[l] + ny[l] * w,next.c[l] = p.c[l];
			  Q.push(next);
			}
		    }
		}
	    }

	}
    }
  
}


void makeEv()
{
  rep(y,MAX*MAX)rep(x,MAX*MAX)ev[y][x] = inf;

  /*
  rep(y,h)rep(x,w)
    {
      deque<ii> deq;
      deq.push_back(ii(x+y*w,0));
      ev[y*w+x][y*w+x] = 0;
      //cout << "cur ( " << x << "," << y << ")\n";
      while(!deq.empty())
	{
	  ii state = deq.front(); deq.pop_front();
	  int cx = state.first % w;
	  int cy = state.first / w;
	  //cout << "state(" << state.first%w << "," << state.first/w << " : " << state.second << ")\n";
	  rep(j,4)
	    {
	      int nx = cx + dx[j];
	      int ny = cy + dy[j];
	      if(!(0 <= nx && nx < w && 0 <= ny && ny < h))continue;
	      if(G[ny][nx] == '#')continue;
	      if(ev[cy*w+cx][ny*w+nx] > state.second + 1)
		{
 		  ev[cy*w+cx][ny*w+nx] = state.second + 1;
		  deq.push_back(ii(nx+ny*w,state.second+1));
		}
	    }
	}
    }
  */

  //int x = 1,y = 3;
  rep(y,h)rep(x,w)
    {

  deque<ii> deq;
  deq.push_back(ii(x+y*w,0));
  ev[x+y*w][x+y*w] = 0;
  while(!deq.empty())
    {
      ii state = deq.front(); deq.pop_front();
      int cx = state.first % w;
      int cy = state.first / w;
      rep(i,4)
	{
	  int nx = cx + dx[i];
	  int ny = cy + dy[i];
	  if(!(0 <= nx && nx < w && 0 <= ny && ny < h))continue;
	  if(G[ny][nx] == '#')continue;
	  if(ev[x+y*w][nx+ny*w] > state.second + 1)
	    {
	      ev[x+y*w][nx+ny*w] = state.second + 1;
	      deq.push_back(ii(nx+ny*w,state.second+1));
	    }
	}
    }


    }

}

void compute()
{
  mincost.clear();

  dex = 0;
  rep(y,h)rep(x,w)
    if('a' <= G[y][x] && G[y][x] <= 'z')
      pp[dex] = x + y * w,cc[dex++] = G[y][x]; 


  rep(i,n)
    {
      char c = cc[i];
      c = (char)('A'+c-'a');
      map<char,int> index;
      rep(y,h)rep(x,w)index[G[y][x]] = y * w + x;
      goal[i] = index[c];
      //cout << "pp = " << pp[i]%w << "," << pp[i]/w << endl;
      //cout << cc[i] << " c = " << c << endl;
      //cout << "goal[" << i << "] = " << goal[i] % w << "," << goal[i] / w << endl;
    }    

  
  priority_queue<P> Q;
  {
    P prep = P(0);
    rep(i,dex)prep.p[i] = pp[i],prep.c[i] = cc[i];
    Q.push(prep);
  }

  int ans = inf;
  while(!Q.empty())
    {
      P p = Q.top(); Q.pop();

      if(p.cost >= ans)continue;

      int add_cost = 0;
      rep(i,n)
	{
	  add_cost = max(add_cost,ev[p.p[i]][goal[i]]);
	  //cout << "e["<<p.p[i]%w << "," <<p.p[i]/w<<"]["<<goal[i]%w << "," << goal[i]/w<<"] = " << ev[p.p[i]][goal[i]] << endl;
	}
      //cout << p.cost << " + " << add_cost << " >= " << ans << endl;
      if(p.cost+add_cost >= ans)continue;


      /*
	char store[n];
	int x[n],y[n];
	rep(i,n)x[i] = p.p[i] % w,y[i] = p.p[i] / w;
	rep(i,n)store[i] = initialD[y[i]][x[i]];
	rep(i,n)initialD[y[i]][x[i]] = p.c[i];
	cout << "cost : " << p.cost << endl;
	print(initialD);
	rep(i,n)initialD[y[i]][x[i]] = store[i];
      */

      if(n == 1)
	{
	  int x = p.p[0] % w;
	  int y = p.p[0] / w;
	  char c = p.c[0];
	  rep(i,5)
	    {
	      int nx = x + dx[i];
	      int ny = y + dy[i];
	      if(!( 0 <= nx && nx < w && 0 <= ny && ny < h ))continue;
	      if(G[ny][nx] == '#')continue;
	      
	      char store = initialD[ny][nx];
	      initialD[ny][nx] = c;
	      ull hsh = getHash(initialD);
	      initialD[ny][nx] = store;
	      if(mincost.find(hsh) == mincost.end())
		{
		  mincost[hsh] = p.cost + 1;
		  if(mincostR.find(hsh) != mincostR.end())
		    {
		      ans = min(ans,p.cost+1+mincostR[hsh]);
		      continue;
		    }
		  P next = P(p.cost+1);
		  next.p[0] = nx + ny * w;
		  next.c[0] = c;
		  Q.push(next);
		}
	    }
	}
      else if(n == 2)
	{
	  assert(p.p[0] != inf && p.p[1] != inf);
	  int x1 = p.p[0] % w;
	  int y1 = p.p[0] / w;
	  int x2 = p.p[1] % w;
	  int y2 = p.p[1] / w;
	  assert(G[y1][x1] != '#' && G[y2][x2] != '#');

	  rep(i,5)
	    {
	      int nx1 = x1 + dx[i];
	      int ny1 = y1 + dy[i];
	      if(!( 0 <= nx1 && nx1 < w && 0 <= ny1 && ny1 < h ))continue;
	      if(G[ny1][nx1] == '#')continue;

	      rep(j,5)
		{
		  int nx2 = x2 + dx[j];
		  int ny2 = y2 + dy[j];
		  if(!( 0 <= nx2 && nx2 < w && 0 <= ny2 && ny2 < h ))continue;
		  if(G[ny2][nx2] == '#')continue;
		  if(!isValidMove(p.p[0],nx1+ny1*w,p.p[1],nx2+ny2*w))continue;

		  char store1 = initialD[ny1][nx1],store2 = initialD[ny2][nx2];
		  initialD[ny1][nx1] = p.c[0];
		  initialD[ny2][nx2] = p.c[1];
		  ull hsh = getHash(initialD);
		  initialD[ny1][nx1] = store1;
		  initialD[ny2][nx2] = store2;

		  if(mincost.find(hsh) == mincost.end())
		    {
		      mincost[hsh] = p.cost + 1;
		      if(mincostR.find(hsh) != mincostR.end())
			{
			  ans = min(ans,p.cost+1+mincostR[hsh]);
			  continue;
			}
		      P next = P(p.cost+1);
		      next.p[0] = nx1 + ny1 * w;
		      next.p[1] = nx2 + ny2 * w;
		      rep(k,2)next.c[k] = p.c[k];//MUDA
		      Q.push(next);
		    }
		}
	    }
	}
      else if(n == 3)
	{

	  int x[3],y[3],nx[3],ny[3];
	  rep(i,3)x[i] = p.p[i] % w, y[i] = p.p[i] / w;

	  rep(i,5)
	    {
	      nx[0] = x[0] + dx[i];
	      ny[0] = y[0] + dy[i];
	      if(!( 0 <= nx[0] && nx[0] < w && 0 <= ny[0] && ny[0] < h ))continue;
	      if(G[ny[0]][nx[0]] == '#')continue;

	      rep(j,5)
		{
		  nx[1] = x[1] + dx[j];
		  ny[1] = y[1] + dy[j];
		  if(!( 0 <= nx[1] && nx[1] < w && 0 <= ny[1] && ny[1] < h ))continue;
		  if(G[ny[1]][nx[1]] == '#')continue;
		  if(!isValidMove(p.p[0],nx[0]+ny[0]*w,p.p[1],nx[1]+ny[1]*w))continue;

		  rep(k,5)
		    {
		      nx[2] = x[2] + dx[k];
		      ny[2] = y[2] + dy[k];
		      if(!( 0 <= nx[2] && nx[2] < w && 0 <= ny[2] && ny[2] < h ))continue;
		      if(G[ny[2]][nx[2]] == '#')continue;
		      if(!isValidMove(p.p[0],nx[0]+ny[0]*w,p.p[2],nx[2]+ny[2]*w))continue;
		      if(!isValidMove(p.p[1],nx[1]+ny[1]*w,p.p[2],nx[2]+ny[2]*w))continue;

		      char store[3];
		      rep(l,3)store[l] = initialD[ny[l]][nx[l]];
		      rep(l,3)initialD[ny[l]][nx[l]] = p.c[l];
		      ull hsh = getHash(initialD);
		      rep(l,3)initialD[ny[l]][nx[l]] = store[l];

		      if(mincost.find(hsh) == mincost.end())
			{
			  mincost[hsh] = p.cost + 1;
			  if(mincostR.find(hsh) != mincostR.end())
			    {
			      ans = min(ans,p.cost+1+mincostR[hsh]);
			      continue;
			    }
			  P next = P(p.cost + 1);
			  rep(l,3)next.p[l] = nx[l] + ny[l] * w,next.c[l] = p.c[l];
			  Q.push(next);
			}
		    }
		}
	    }

	}
    }
  printf("%d\n",ans);
  //cout << ans << endl; 
}

int main()
{
  //clock_t st,ed;
  //st = clock();
  while(scanf("%d %d %d",&w,&h,&n),w|h|n)
    {
      rep(i,h)
	{
	  getchar();
	  rep(j,w)
	    scanf("%c",&G[i][j]);
	}
      preComputing(28);//大きくするとMLE、小さくするとTLE
      makeEv();
      compute();

    }

  //ed = clock();
  //cout << setiosflags(ios::fixed) << setprecision(10) << "time : " << (double)(ed-st)/CLOCKS_PER_SEC << endl;

  return 0;
}

Compiler output:
a.cc: In function 'ull getHash(char (*)[17])':
a.cc:77:11: error: reference to 'hash' is ambiguous
   77 |           hash[i][j] = e;
      |           ^~~~
In file included from /usr/include/c++/14/string_view:50,
                 from /usr/include/c++/14/bits/basic_string.h:47,
                 from /usr/include/c++/14/string:54,
                 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/functional_hash.h:59:12: note: candidates are: 'template<class _Tp> struct std::hash'
   59 |     struct hash;
      |            ^~~~
a.cc:42:5: note:                 'ull hash [17][17]'
   42 | ull hash[MAX][MAX],tmp[MAX][MAX];
      |     ^~~~
a.cc:81:10: error: reference to 'hash' is ambiguous
   81 |   return hash[0][0];
      |          ^~~~
/usr/include/c++/14/bits/functional_hash.h:59:12: note: candidates are: 'template<class _Tp> struct std::hash'
   59 |     struct hash;
      |            ^~~~
a.cc:42:5: note:                 'ull hash [17][17]'
   42 | ull hash[MAX][MAX],tmp[MAX][MAX];
      |     ^~~~