View Code of Problem 1010

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<functional>
using namespace std;
typedef unsigned long long ull;
typedef long long LL;
const int low(int x){ return x&-x; }
const int maxn = 2e2 + 10;
int n, m, map[maxn][maxn], tot, dis[maxn][maxn], goal, flag;
char s[maxn][maxn];

struct MaxFlow
{
	const static int maxe = 1e6 + 10;    //边数
	const static int maxp = 1e5 + 10;   //点数
	const static int INF = 0x7FFFFFFF;
	struct Edges
	{
		int to, flow;
		Edges(){}
		Edges(int to, int flow) :to(to), flow(flow){}
	}edge[maxe];
	int first[maxp], next[maxe], dis[maxp], tot, work[maxp], n;

	void clear(int x){ n = x; tot = 0; for (int i = 0; i <= n; i++) first[i] = -1; }

	void AddEdge(int s, int t, int flow)
	{
		edge[tot] = Edges(t, 0); next[tot] = first[s]; first[s] = tot++;
		edge[tot] = Edges(s, flow);    next[tot] = first[t]; first[t] = tot++;
	}

	bool bfs(int s, int t)
	{
		for (int i = 0; i <= n; i++) dis[i] = -1;
		queue<int> p;    p.push(s);    dis[s] = 0;
		while (!p.empty())
		{
			int q = p.front();    p.pop();
			for (int i = first[q]; i != -1; i = next[i])
			{
				if (edge[i ^ 1].flow&&dis[edge[i].to] == -1)
				{
					p.push(edge[i].to);
					dis[edge[i].to] = dis[q] + 1;
					if (dis[t] != -1) return true;
				}
			}
		}
		return false;
	}

	int dfs(int s, int t, int low)
	{
		if (s == t) return low;
		for (int &i = work[s]; i >= 0; i = next[i])
		{
			if (dis[s] + 1 == dis[edge[i].to] && edge[i ^ 1].flow)
			{
				int x = dfs(edge[i].to, t, min(low, edge[i ^ 1].flow));
				if (x)
				{
					edge[i].flow += x;    edge[i ^ 1].flow -= x;
					return x;
				}
			}
		}
		return 0;
	}

	int dinic(int s, int t)
	{
		int maxflow = 0, inc = 0;
		while (bfs(s, t))
		{
			for (int i = 0; i <= n; i++) work[i] = first[i];
			while (inc = dfs(s, t, INF)) maxflow += inc;
		}
		return maxflow;
	}
}solve;

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

void dfs(int x, int y, int u, int v)
{
	if (x == u&&y == v) return;
	if (map[x][y]>0 && map[x][y] <= goal) solve.AddEdge(map[x][y], map[u][v], 1);
	for (int i = 0; i < 4; i++)
	{
		if (dis[x][y] == dis[x + a[i]][y + b[i]] + 1)
			dfs(x + a[i], y + b[i], u, v);
	}
	dis[x][y] = -1;
}

void bfs(int x, int y)
{
	for (int i = 0; i <= n + 1; i++)
	for (int j = 0; j <= m + 1; j++) dis[i][j] = -1;
	queue<int> p;
	dis[x][y] = 0;
	int u = 0, v = 0;
	p.push((x - 1)*m + y);
	while (!p.empty())
	{
		int q = p.front(); p.pop();
		u = (q - 1) / m + 1, v = (q - 1) % m + 1;
		if (map[u][v] == map[x][y] + 1) break;
		for (int i = 0; i < 4; i++)
		{
			if (map[u + a[i]][v + b[i]] >= 0)
			{
				if (dis[u + a[i]][v + b[i]] == -1)
				{
					dis[u + a[i]][v + b[i]] = dis[u][v] + 1;
					p.push((u + a[i] - 1)*m + v + b[i]);
				}
			}
		}
	}
	if (map[u][v] == map[x][y] + 1) dfs(u, v, x, y); else flag = 0;
}

int main()
{
	while (scanf("%d%d", &n, &m) != EOF)
	{
		tot = 0;			flag = 1;
		memset(map, -1, sizeof(map));
		for (int i = 1; i <= n; i++)
		{
			scanf("%s", s[i] + 1);
			for (int j = 1; j <= m; j++)
			{
				if (s[i][j] == '.') map[i][j] = 0;
				else if (s[i][j] == '#') map[i][j] = -1;
				else if (s[i][j] == '*') map[i][j] = ++tot;
			}
		}
		goal = tot;
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= m; j++)
			{
				if (s[i][j] != '*'&&s[i][j] != '.'&&s[i][j] != '#')
				{
					if (s[i][j] <= 'Z') map[i][j] = goal + s[i][j] - 'A' + 1;
					else map[i][j] = goal + s[i][j] - 'a' + 27;
					tot = max(tot, map[i][j]);
				}
			}
		}
		solve.clear(tot);
		for (int i = 1; i <= n&&flag; i++)
		{
			for (int j = 1; j <= m&&flag; j++)
			{
				if (map[i][j] > goal&&map[i][j] < tot)
				{
					bfs(i, j); solve.AddEdge(map[i][j], tot, 1);
				}
				else if (map[i][j]>0 && map[i][j] <= goal)
				{
					solve.AddEdge(0, map[i][j], 1);
				}
			}
		}
		if (flag) printf("%d\n", solve.dinic(0, tot)); else printf("-1\n");
	}
	return 0;
}