题意：

A-Z&&a-z 表示 集结点

从A点出发经过 最短步数 走到下一个集结点（A的下一个集结点为B ，Z的下一个集结点为a） 的路上遇到金子（*）则能够捡走（一个点仅仅能捡一次）

求从A点出发走遍全部的的集结点 最多能捡多少金子

思路：先对于第 i 个集结点用BFS求出 对于每一个点从该集结点所需的步数  为D[ I ] [ t ]

对于随意一个金子若  两个相邻的集结点的最短步数=其到该金子的步数和 则建一条边（能够拿）

然后最大流求

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <string>

#include <iostream>

#include <algorithm>

#include <sstream>

#include <cmath>

using namespace std;

#include <queue>

#include <stack>

#include <vector>

#include <deque>

#include <set>

#include <map>

#include <time.h>;

#define cler(arr, val)    memset(arr, val, sizeof(arr))

#define FOR(i,a,b)  for(int i=a;i<=b;i++)

#define IN   freopen ("in.txt" , "r" , stdin);

#define OUT  freopen ("out.txt" , "w" , stdout);

typedef long long  LL;

const int MAXN = 10014;

const int MAXM = 41001;

const int INF = 0x3f3f3f3f;

const int mod = 1000000007;

struct Edge

{

    int to,next,cap,flow;

} edge[MAXM]; //注意是MAXM

int tol;

int head[MAXN];

int gap[MAXN],dep[MAXN],cur[MAXN];

void init()

{

    tol = 0;

    memset(head,-1,sizeof (head));

}

void addedge (int u,int v,int w,int rw = 0)

{

    edge[tol].to = v;

    edge[tol].cap = w;

    edge[tol].flow = 0;

    edge[tol].next = head[u];

    head[u] = tol++;

    edge[tol].to = u;

    edge[tol].cap = rw;

    edge[tol].flow = 0;

    edge[tol].next = head[v];

    head[v] = tol++;

}

int Q[MAXN];

void BFS(int start,int end)

{

    memset(dep,-1,sizeof(dep));

    memset(gap,0,sizeof(gap));

    gap[0] = 1;

    int front = 0, rear = 0;

    dep[end] = 0;

    Q[rear++] = end;

    while(front != rear)

    {

        int u = Q[front++];

        for(int i = head[u]; i !=  -1; i = edge[i].next)

        {

            int v = edge[i]. to;

            if(dep[v] != -1)continue;

            Q[rear++] = v;

            dep[v] = dep[u] + 1;

            gap[dep[v]]++;

        }

    }

}

int S[MAXN];

int sap(int start,int end, int N)

{

    BFS(start,end);

    memcpy(cur,head,sizeof(head));

    int top = 0;

    int u = start;

    int ans = 0;

    int i;

    while(dep[start] < N)

    {

        if(u == end)

        {

            int Min = INF;

            int inser;

            for( i = 0; i < top; i++)

            {

                if(Min > edge[S[i]].cap - edge[S[i]].flow)

                {

                    Min = edge[S[i]].cap - edge[S[i]].flow;

                    inser = i;

                }

            }

            for( i = 0; i < top; i++)

            {

                edge[S[i]]. flow += Min;

                edge[S[i]^1].flow -= Min;

            }

            ans += Min;

            top = inser;

            u = edge[S[top]^1].to;

            continue;

        }

        bool flag =  false;

        int v;

        for( i = cur[u]; i != -1; i = edge[i]. next)

        {

            v = edge[i]. to;

            if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u])

            {

                flag =  true;

                cur[u] = i;

                break;

            }

        }

        if(flag)

        {

            S[top++] = cur[u];

            u = v;

            continue;

        }

        int Min = N;

        for( i = head[u]; i !=  -1; i = edge[i].next)

        {

            if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min)

            {

                Min = dep[edge[i].to];

                cur[u] = i;

            }

        }

        gap[dep[u]]--;

        if(!gap[dep[u]]) return ans;

        dep[u] = Min + 1;

        gap[dep[u]]++;

        if(u != start)u = edge[S[--top]^1].to;

    }

    return ans;

}

char s[103][103];

bool vis[103][103];

int goal[103*103];

int ral[103*103];

int d[53][101*101];

int n,m;

int xx[4]= {1,0,-1,0};

int yy[4]= {0,-1,0,1};

void bfs(int x)

{

    memset(d[x],INF,sizeof(d[x]));

    cler(vis,false);

    queue<int>q;

    int t=ral[x];

    vis[t/m][t%m]=true;

    d[x][t]=0;

    q.push(t);

    while(!q.empty())

    {

        t=q.front();

        q.pop();

        int nx=t/m,ny=t%m;

        for(int i=0; i<4; i++)

        {

            int dx=nx+xx[i],dy=ny+yy[i];

            if(dx>=0&&dx<n&&dy>=0&&dy<m&&!vis[dx][dy]&&s[dx][dy]!='#')

            {

                vis[dx][dy]=true;

                d[x][dx*m+dy]=d[x][t]+1;

                q.push(dx*m+dy);

            }

        }

    }

}

int find(char c)

{

    if('A'<=c&&c<='Z')

        return c-'A';

    if('a'<=c&&c<='z')

        return c-'a'+26;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

#endif

    while(~scanf("%d%d",&n,&m))

    {

        init();

        cler(ral,0);

        int tol1=0,tol2=0;

        for(int i=0; i<n; i++)

        {

            scanf("%s",s[i]);

            for(int j=0; j<m; j++)

            {

                if(isalpha(s[i][j]))

                {

                    ral[find(s[i][j])]=i*m+j;

                    tol1++;

                }

                else if(s[i][j]=='*')

                    goal[tol2++]=i*m+j;

            }

        }

        for(int i=0; i<tol1; i++)

            bfs(i);

        int flag=0;

        for(int i=1; i<tol1; i++)

            for(int j=0; j<tol2; j++)

            {

                if(d[i][goal[j]]+d[i-1][goal[j]]==d[i-1][ral[i]])

                    addedge(i,tol1+j,1);

                if(d[i-1][ral[i]]==INF)

                    flag=1;

            }

        if(flag)

            printf("-1\n");

        else

        {

            for(int i=1;i<tol1;i++)

                addedge(0,i,1);

            for(int i=0;i<tol2;i++)

                addedge(tol1+i,tol1+tol2,1);

            printf("%d\n",sap(0,tol1+tol2,tol1+tol2+1));

        }

    }

    return 0;

}