HDU 3468 Treasure Hunting(二分匹配+最短路)

#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int N = 127;
const int inf = 1061109567;
const int INF = 0x3f3f3f3f;
const int dx[] = {-1,1,0,0};
const int dy[] = {0,0,-1,1};
struct Hungary     //二分匹配模板 =-=
{vector<int>G[N];//二分图左边的点最多只有52个，这里G[N] N 大于 52 即可int linker[N*N];//二维坐标换算成一维的点，最大能达到N*Nbool vis[N*N];bool dfs(int u){for (int i = 0;i < G[u].size();++i){int &t = G[u][i];if (!vis[t]){vis[t] = 1;if (linker[t] == -1||dfs(linker[t])){linker[t] = u;return 1;}}}return 0;}int hungary(int n)//用的匈牙利算法，传入的n是二分图左边点的个数{int res = 0;mem(linker,-1);for (int u = 1;u <= n;++u){mem(vis,0);if (dfs(u)) res++;}return res;}
}ans;
int go[N];//两人汇合（字母）的位置    最多52个
int gold[N*N];//金币的位置    最多N*N个
int d[N][N*N];//距离      d[i][gold[j]]表示第i个字母到金币gold[j]（第j个金币的一维编号）的距离
char mp[N][N];//保存输入的地图
bool vis[N*N];
int r,c;//行，列
int mx;
bool bfs(int s)
{mem(vis,0);mem(d[s],INF);queue<int>q;q.push(go[s]);vis[go[s]] = 1;d[s][go[s]] = 0;while (!q.empty()){int h = q.front();q.pop();int x = (h-1)/c;int y = (h-1)%c;//一维换算成二维坐标for (int i = 0;i < 4;++i){int xx = x + dx[i];int yy = y + dy[i];if (xx>=0&&yy>=0&&xx<r&&yy<c){int nx = xx*c + yy + 1;if (mp[xx][yy] == '#') continue;if (vis[nx]) continue;q.push(nx);d[s][nx] = d[s][h] + 1;//记录距离vis[nx] = 1;}}}if (s == mx) return 1;//最后一个汇合点  不需要判断能否走到下一个点，但是还是要bfs求出距离d
//    cout<<"d["<<s<<"]["<<go[s+1]<<"] = "<<d[s][go[s+1]]<<endl;if (d[s][go[s+1]] != inf)return 1;else return 0;//能不能走到下一个汇合点
}
int judge(char c)
{if (isalpha(c)){if (c >= 'A'&&c <= 'Z') return c-'A'+1;if (c >= 'a'&&c <= 'z') return c - 'a' + 1 + 26;}return 0;
}
int main()
{while (~scanf("%d %d",&r,&c)){mem(go,-1);mem(ans.G,0);int tot = 1;mx = 0;for (int i = 0;i < r;++i){scanf("%s",mp[i]);for (int j = 0;j < c;++j){int t = judge(mp[i][j]);if (t){go[t] = i*c + j + 1;//取一维编号mx = max(mx,t);//mx保存的是最后一个字母}else if (mp[i][j] == '*'){gold[tot] = i*c + j + 1;tot++;}}}bool ok = 1;for (int i = 1;i <= mx;++i) //bfs跑最短路{if (go[i] == -1)//这句是为了防止有 A B D这样的输入（即跳过了字母C）{ok = 0;break;}if (!bfs(i))//不能到达汇合点{ok = 0;break;}}if (!ok){puts("-1");continue;}for (int i = 1;i < mx;++i)  //选择金币建图{for (int j = 1;j < tot;++j){if (d[i][go[i+1]] == d[i][gold[j]] + d[i+1][gold[j]])//如果某金币到起点终点距离之和等于起点到终点的距离{ans.G[i].push_back(gold[j]);//这个金币在最短路上，则在该金币和起点之间连一条线}}}printf("%d\n",ans.hungary(mx));}return 0;
}
/*
input 2 4
A.B.
***C2 4
A#B.
***C2 4
A#B.
*#*C3 4
A#B.
..*.
C...2 4
C#B.
***A3 5
.A**.
C*...
..B..output12-1122
*/