#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits.h>
using namespace std;
typedef long long LL;
const int MAXN=1e+5;
const int MAXM=1e+6;
const int INF = INT_MAX;
struct Edge
{
int from,to,ci,next;
Edge(){}
Edge(int _from,int _to,int _ci,int _next):from(_from),to(_to),ci(_ci),next(_next){}
}e[MAXM];
int head[MAXN],tot;
int dis[MAXN];
int top,sta[MAXN],cur[MAXN];
inline void init(){
memset(head,-1,sizeof(head));
tot=0;
}
inline void AddEdge(int u,int v,int ci0,int ci1=0){
e[tot]=Edge(u,v,ci0,head[u]);
head[u]=tot++;
e[tot]=Edge(v,u,ci1,head[v]);
head[v]=tot++;
}
inline bool bfs(int st,int et){
memset(dis,0,sizeof(dis));
dis[st]=1;
queue <int> q;
q.push(st);
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=head[now];i!=-1;i=e[i].next){
int next=e[i].to;
if(e[i].ci&&!dis[next]){
dis[next]=dis[now]+1;
if(next==et)return true;
q.push(next);
}
}
}
return false;
}
LL Dinic(int st,int et){
LL ans=0;
while(bfs(st,et)){
top=0;
memcpy(cur,head,sizeof(head));
int u=st,i;
while(1){
if(u==et){
int pos,minn=INF;
for(i=0;i<top;i++)
{
if(minn>e[sta[i]].ci){
minn=e[sta[i]].ci;
pos=i;
}
}
for(i=0;i<top;i++){
e[sta[i]].ci-=minn;
e[sta[i]^1].ci+=minn;
}
top=pos;
u=e[sta[top]].from;
ans+=minn;
}
for(i=cur[u];i!=-1;cur[u]=i=e[i].next)
if(e[i].ci&&dis[u]+1==dis[e[i].to])break;
if(cur[u]!=-1){
sta[top++]=cur[u];
u=e[cur[u]].to;
}
else {
if(top==0)break;
dis[u]=0;
u=e[sta[--top]].from;
}
}
}
return ans;
}
struct point
{
char pos;
int x,y;
point(){}
point(char _pos,int _x,int _y):pos(_pos),x(_x),y(_y){}
}cs[110];
bool cmp(point x,point y){
return x.pos<y.pos;
}
char map1[110][110];
int disx[2][110][110],n,m;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int bfs(point st,point et,int fl){
pair <int,int> now,next;
queue < pair<int,int> > q;
q.push(pair<int,int>(st.x,st.y));
memset(disx[fl],-1,sizeof(disx[fl]));
disx[fl][st.x][st.y]=0;
while(!q.empty()){
now=q.front();
q.pop();
if(now.first==et.x&&now.second==et.y)return disx[fl][now.first][now.second];
for(int i=0;i<4;i++){
next.first=now.first+dx[i];
next.second=now.second+dy[i];
if(next.first<1||next.first>n||next.second<1||next.second>m)continue;
if(map1[next.first][next.second]=='#')continue;
if(disx[fl][next.first][next.second]!=-1)continue;
disx[fl][next.first][next.second]=disx[fl][now.first][now.second]+1;
q.push(next);
}
}
return -1;
}
int main()
{
while(~scanf("%d%d",&n,&m)){
int tos1=0;
init();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf(" %c",&map1[i][j]);
if(map1[i][j]!='.'&&map1[i][j]!='*'&&map1[i][j]!='#'){
cs[tos1++]=point(map1[i][j],i,j);
}
}
sort(cs,cs+tos1,cmp);
int flag=1;
for(int i=0;i<tos1-1&&flag;i++){
int t1=bfs(cs[i],cs[i+1],0);
int t2=bfs(cs[i+1],cs[i],1);
if(t1==-1){ flag=0;break; }
for(int ii=1;ii<=n;ii++)
for(int jj=1;jj<=m;jj++)
if(disx[0][ii][jj]!=-1&&disx[1][ii][jj]!=-1)
if(disx[0][ii][jj]+disx[1][ii][jj]==t1){
if(map1[ii][jj]=='*'){
AddEdge(ii*m+jj+200,cs[i+1].pos,1);
}
}
}
if(flag){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
AddEdge(0,i*m+j+200,1);
for(int i=0;i<tos1;i++)
AddEdge(cs[i].pos,1,1);
printf("%I64d\n",Dinic(0,1));
}
else puts("-1");
}
return 0;
}
|
