Language: C++

#include<iostream>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<algorithm>
using namespace std;
#define SIZE 16
#define INF (1 << 21)
int dx[]={0,0,1,-1,0};
int dy[]={1,-1,0,0,0};
short cost[3][16][16];
string m[16];
void bfs(int row,int column,int num,int ini);
class ghost{
public:
  int p[3],n;
  bool operator<(const ghost & a)const{
    for(int i=0;i<3;i++){
      if ( p[i] == a.p[i])continue;
      else return p[i] < a.p[i];
    }
    return false;;
  }
  int calc(int column){
    int ret = 0;
    for(int i=0;i<n;i++){
      ret = max(ret,cost[i][p[i]/column][p[i]%column]);
    }
    return ret;
  }
};

class state{
public:
  ghost data;
  int cnt,h;
  bool operator<(const state & a)const{
    return cnt+h > a.cnt + a.h;
    if ( cnt+h == a.cnt+a.h)return cnt > a.cnt;
    return cnt+h > a.cnt+a.h;
  }
  bool move(int num,int direc,int row,int column){
    int x= data.p[num]%column,y=data.p[num]/column;
    int nex = x+dx[direc],ney =y+dy[direc];
    if ( nex < 0 || ney<0 || nex >=column || ney>=row||m[ney][nex]=='#')return false;
    data.p[num]=nex+ney*column;
    return true;
  }
  bool legal(const state & source){
    for(int i=0;i<data.n;i++){
      for(int j=0;j<data.n;j++){
	if ( i == j)continue;
	if ( data.p[i] == data.p[j])return false;
	if ( data.p[i] == source.data.p[j] && 
	     data.p[j] == source.data.p[i])return false;
      }
    }
    return true;
  }
};

void dfs(int row,int column,priority_queue<state> &Q,const state &source,
	 state  dest,set<ghost>& S,int now,int n){
  if ( n == now){
    if ( dest.legal(source) && S.find(dest.data) == S.end()){
      dest.h = dest.data.calc(column);
      dest.cnt++;
      S.insert(dest.data);
      Q.push(dest);
    }
    return;
  }
  state temp = dest;
  int chx,chy;
  for(int i=0;i<5;i++){
    dest = temp;
    if (dest.move(now,i,row,column));
    else continue;
    dfs(row,column,Q,source,dest,S,now+1,n);
	
  }
}


int a_star(int row,int column,ghost ini){
  state first = {ini,0,ini.calc(column)};
  priority_queue<state> Q;
  set<ghost> S;
  S.insert(ini);
  Q.push(first);
  while(!Q.empty()){
    state now = Q.top();
    Q.pop();
    if (now.h == 0)return now.cnt;
    dfs(row,column,Q,now,now,S,0,ini.n);
  }
  return -1;
}



main(){
  int column,row,n;
  while(cin >> column >> row >> n && n ){
    cin.ignore();
    for(int i=0;i<row;i++){
      getline(cin,m[i]);
    }// end for taking inputdat a
    ghost ini;
    ini.n = n;
    for(int i=0;i<row;i++){
      for(int j=0;j<column;j++){
	if ( isupper(m[i][j])){
	  bfs(row,column,m[i][j]-'A',i*column+j);
	}else if ( islower(m[i][j])){
	  ini.p[m[i][j]-'a'] = i*column+j;
	}
      }
    }//end for initialization loop

    cout << a_star(row,column,ini) << endl;
  }
}



void bfs(int row,int column,int num,int ini){
  queue<int> Q;
  Q.push(ini);
  for(int i=0;i<row;i++){
    for(int j=0;j<column;j++){
      cost[num][i][j] = INF;
    }
  }
  cost[num][ini/column][ini%column]=0;
  while(!Q.empty()){
    int now = Q.front();
    int x=now%column,y=now/column;
    Q.pop();
    for(int i=0;i<4;i++){
      int nex = x+dx[i],ney = y+dy[i];
      if ( nex < 0 || ney < 0 || nex >=column || ney >=row || m[ney][nex]=='#')
	continue;
      if ( cost[num][y][x] +1 < cost[num][ney][nex]){
	cost[num][ney][nex]=cost[num][y][x]+1;
	Q.push(ney*column+nex);
      }
    }
  }
  /*
  cout << "bfs for " << num<< " th ghoast" << endl;
  for(int i=0;i<row;i++){
    for(int j=0;j<column;j++){
      if ( cost[num][i][j] == INF)cout << "x  ";
      else cout << cost[num][i][j] << "  ";
    }
    cout << endl;
  }
  cout << endl;
  */
}

Compiler output:
a.cc: In member function 'int ghost::calc(int)':
a.cc:28:16: error: no matching function for call to 'max(int&, short int&)'
   28 |       ret = max(ret,cost[i][p[i]/column][p[i]%column]);
      |             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/string:51,
                 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/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
a.cc:28:16: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'short int')
   28 |       ret = max(ret,cost[i][p[i]/column][p[i]%column]);
      |             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note:   candidate expects 3 arguments, 2 provided
In file included from /usr/include/c++/14/algorithm:61,
                 from a.cc:6:
/usr/include/c++/14/bits/stl_algo.h:5706:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
 5706 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5706:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5716:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
 5716 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5716:5: note:   template argument deduction/substitution failed:
a.cc:28:16: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   28 |       ret = max(ret,cost[i][p[i]/column][p[i]%column]);
      |             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc: At global scope:
a.cc:103:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  103 | main(){
      | ^~~~
a.cc: In function 'void bfs(int, int, int, int)':
a.cc:9:16: warning: overflow in conversion from 'int' to 'short int' changes value from '2097152' to '0' [-Woverflow]
    9 | #define INF (1 << 21)
      |             ~~~^~~~~~
a.cc:133:25: note: in expansion of macro 'INF'
  133 |       cost[num][i][j] = INF;
      |                         ^~~