開始建圖打搓了，參考了大牛的題解打的版本比較清爽，後來改的基本雷同了http://www.cnblogs.com/woaishizhan/archive/2013/04/08/3008719.html 題意：給定n，m表示下面地圖大小 .表示空地 #表示牆 *表示黃金 行走的路線是A->Z->a->z 規則，必須從字母依次走最短路到下一個字母（字母必須連續走，如果走不到下一個字母或者地圖上不存在下一個字母則輸出-1） 每次走到下一個字母可以取走路途上的一個黃金，問最多能取走幾個黃金 思路：走到最後一個字母就結束了，所以希望從每個字母走出來都能得到一個黃金，所以是二分匹配 把起點字母作為X集， 黃金作為Y集， 映射條件是黃金在 字母間行走的最短路上 然後這裡用BFS尋找路徑建圖 最後套個二分匹配的模版
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<set>
#include<math.h>
#include<string.h>
#include<queue>
#include<vector>
#define N 105
#define inf 999999999
using namespace std;
int n,M;
int road[N],p[N*N],gold[N*N],num,pn;//road 表示字母在p中的編號，p是字母的坐標（一維化）
int dis[N][N*N];//dis[a][b] 表示離散化的字母點a到 一維化的坐標b的距離
char map[N][N];
vector<int>G[N];
int go[4][2]={1,0,0,1,-1,0,0,-1};
void bfs(int s){
bool vis[N*N];
memset(vis,0,sizeof(vis));
queue<int>q;
memset(dis[s],-1,sizeof(dis[s]));
dis[s][p[s]]=0;
q.push(p[s]);
vis[p[s]]=1;
while(!q.empty())
{
int t=q.front();
int x=t/M,y=t%M;
q.pop() ;
for(int i=0;i<4;i++)
{
int nowx=x+go[i][0],nowy=y+go[i][1];
int now=nowx*M+nowy;
if(map[nowx][nowy]=='#')continue;
if(nowx<0 || nowx>=n ||nowy<0||nowy>=M)continue;
if(vis[now])continue;
vis[now]=1;
dis[s][now]=dis[s][t]+1;
q.push(now);
}
}
}
int lef[N*N];//lef[v]表示右邊點v 當前連接的點
bool T[N*N];//右邊的點是否連過
bool match(int x)
{
for(int i=0;i<G[x].size();i++)
{
int v=G[x][i];
if(!T[v])
{
T[v]=true;
if(lef[v]==-1||match(lef[v]))
{
lef[v]=x;
return true;
}
}
}
return false;
}
void solve()
{
int ans=0;
memset(lef,-1,sizeof(lef));
for(int i=0;i<pn-1;i++)//左右點集匹配，左點集是 0-(pn-1) 右點集是G[左點].size()
{
memset(T,0,sizeof(T));
if(match(i))ans++;
}
printf("%d\n",ans);
}
int f(char c){
if('A'<=c && c<='Z')return c-'A';
else if('a'<=c && c<='z')return c-'a'+26;
}
int main(){
int i,j;
while(~scanf("%d%d",&n,&M)){
pn=num=0;
memset(road,-1,sizeof(road));//這句沒有最後第二個案例過不了
for(i=0;i<n;i++)
{
scanf("%s",map[i]);
for(j=0;j<M;j++)
if(isalpha(map[i][j]))
{
p[pn]=i*M+j;
road[f(map[i][j])]=pn;
pn++;
}
else if(map[i][j]=='*')
{
gold[num++]=i*M+j;
}
}
for(i=0;i<pn;i++)bfs(i),G[i].clear();
for(i=0;i<pn-1;i++)
{
if(road[i]==-1||road[i+1]==-1) break;
if(dis[road[i]][p[road[i+1]]]==-1) break;
}
if(i!=pn-1){puts("-1");continue;}
for(i=0;i<pn-1;i++)
for(j=0;j<num;j++)
{
if(dis[road[i]][gold[j]]==-1 || dis[road[i+1]][gold[j]]==-1)continue;//j這點的黃金到不了字母點
if(dis[road[i]][gold[j]]+dis[road[i+1]][gold[j]]==dis[road[i]][p[road[i+1]]])
G[i].push_back(j);
}
solve();
}
return 0;
}
/*
3 4
A#B.
***C
.D..
4 4
A#B.
***C
.D..
..E*
4 4
A#B.
***C
.D..
.*E*
4 4
A#B.
***C
.D#.
.#E*
4 4
A#B.
***C
.D#.
.#E.
4 4
A#B.
***C
.D##
.#E.
4 4
A#B.
***C
.D#*
.#E.
4 4
a#b.
***c
.d#*
.#e.
4 4
A#B*
*.*C
..D#
E*..
ans;
3
3
4
4
3
-1
4
-1
4
*/
