View Code of Problem 1010

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<cctype>
#include<string>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;

#define end() return 0

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;

const int maxN = 100 + 5;
const int maxn = 10000 + 5;
const int maxv = 100000 + 5;
const int INF = 0x7f7f7f7f;

struct Node{
    int x,y;
    Node(){}
    Node(int _x,int _y):x(_x),y(_y){}
}rally[60];

int C,R;
char str[maxN][maxN];
int dist[60][10005];
int gold[10005],go;
bool vis[maxN][maxN];
int ra,tail;
vector<int>graph[60];
int match[maxn];
bool vist[maxn];

void init(){
    ra=-1; go=0;
    memset(dist,INF,sizeof(dist));
    memset(match,-1,sizeof(match));
    for(int i=0;i<60;i++) graph[i].clear();
}

int get_rally(char s){
    if(s>='A'&&s<='Z') return s-'A'+1;
    if(s>='a'&&s<='z') return s-'a'+27;
    return 0;
}

void input(){
    for(int i=0;i<C;i++){
        scanf("%s",str[i]);
        for(int j=0;j<R;j++){
            if(str[i][j]=='*') gold[go++]=i*R+j;
            else{
                int idx=get_rally(str[i][j]);
                if(idx){ rally[idx]=Node(i,j); ra=max(ra,idx);}
            }
        }
    }
}

int X[]={0,-1,0,1};
int Y[]={-1,0,1,0};

void bfs(int idx,Node s){
    memset(vis,false,sizeof(vis));
    queue<Node>q;
    while(!q.empty()) q.pop();
    q.push(s);
    vis[s.x][s.y]=true;
    dist[idx][s.x*R+s.y]=0;
    while(!q.empty()){
        Node p=q.front();q.pop();
        for(int i=0;i<4;i++){
            int xx=p.x+X[i];
            int yy=p.y+Y[i];
            if(xx>=0&&xx<C&&yy>=0&&yy<R&&!vis[xx][yy]&&str[xx][yy]!='#'){
                vis[xx][yy]=true;
                q.push(Node(xx,yy));
                dist[idx][xx*R+yy]=dist[idx][p.x*R+p.y]+1;
            }
        }
    }

}

void createGraph(){
    for(int i=1;i<ra;i++){
        int idx=rally[i+1].x*R+rally[i+1].y;
        for(int j=0;j<go;j++){
            if(dist[i][gold[j]]+dist[i+1][gold[j]]==dist[i][idx])
                graph[i].push_back(ra+j+1);
        }
    }
}

bool dfs(int u){
    for(int i=0;i<graph[u].size();i++){
        int v=graph[u][i];
        if(!vist[v]){
            vist[v]=true;
            if(match[v]==-1 || dfs(match[v])){
                match[v]=u;
                return true;
            }
        }
    }return false;
}

void solve(){
    for(int i=1;i<=ra;i++){
        bfs(i,rally[i]);
    }
    if(ra==1) {
        printf("-1\n");
        return ;
    }
    for(int i=1;i<ra;i++){
        int idx=rally[i+1].x*R+rally[i+1].y;
        if(dist[i][idx]==INF){
            printf("-1\n");
            return ;
        }
    }
    createGraph();
    int ans=0;
    for(int i=1;i<ra;i++){
        memset(vist,false,sizeof(vist));
        if(dfs(i)) ans++;
    }
    printf("%d\n",ans);
}

int main(){
    while(scanf("%d%d",&C,&R)!=EOF){
        init();
        input();
        solve();
    }end();
}