# 題目: UVa 11380 - Down Went The Titanic

# 題目說明

給一個X * Y的圖，求*(人)能走到#(終點)的最大數量

---

INPUT:
輸入三個整數X、Y、P
接著輸入X * Y個char

---

OUTPUT:
輸出*(人)能走到#(終點)的最大數量

# 解題方法

點上的capacity可視為兩個相連的點，連線的capacity為點上的capacity
再根據上 下 左 右中可以走的點做連接
最後跑Ford Fulkerson演算法，得出maximum flow

# 參考程式碼

#include <iostream>
#include <memory.h>
#include <climits>
#include <queue>

using namespace std;

int X, Y, P;
int _s = 0, _t;
char c;
int G[2000][2000];
int p[2000];
bool vis[2000];
int m[4][2] = { {0, 1}, {1, 0}, {-1, 0}, {0, -1} };

void fast_io()
{
	ios::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);
}

void init()
{
	memset(G, 0, sizeof(G));
	memset(p, 0, sizeof(p));
}

void read_build()
{
	int node = X * Y;
	_t = node * 2 + 1;

	for (int j = 0; j < Y; ++j) for (int i = 0; i < X; ++i)
	{
		int u = X * j + i + 1;
		cin >> c;

		if (c == '.') G[u][u + node] = 1;
		else if (c == '@') G[u][u + node] = INT_MAX;
		else if (c == '*')
		{
			G[u][u + node] = 1;
			G[_s][u] = 1;
		}
		else if (c == '#')
		{
			G[u][u + node] = INT_MAX;
			G[u + node][_t] = P;
		}

		for (int k = 0; k < 4; ++k)
		{
			int x = i + m[k][0];
			int y = j + m[k][1];

			if (x >= 0 && y >= 0 && x < X && y < Y)
			{
				int v = X * y + x + 1;
				G[u + node][v] = INT_MAX;
			}
		}
	}
}

int findflow(int u, int v, int c)
{
	if (v == _s) return c;
	c = findflow(p[u], u, min(G[u][v], c));
	G[u][v] -= c;
	G[v][u] += c;
	return c;
}

int maxflow()
{
	int ret = 0;

	while (1)
	{
		memset(vis, false, sizeof(vis));

		queue<int> Q;
		Q.emplace(_s);
		vis[_s] = true;

		while (!Q.empty() && !vis[_t])
		{
			int u = Q.front();
			Q.pop();

			for (int i = 0; i <= _t; ++i) if (!vis[i] && G[u][i] > 0)
			{
				Q.emplace(i);
				vis[i] = true;
				p[i] = u;
			}
		}

		if (!vis[_t]) break;
		ret += findflow(p[_t], _t, INT_MAX);
	}

	return ret;
}

int main()
{
	fast_io();

	while (cin >> Y >> X >> P)
	{
		init();
		read_build();
		cout << maxflow() << "\n";
	}
}

# 參考資料

https://www.larrysprognotes.com/UVa-11380/