78E - Evacuation - CodeForces Solution

/*
    
███████╗  ░░░░░░  ██╗░░██╗  ███████╗  ███╗░░██╗  ███████╗
╚════██║  ░░░░░░  ██║░██╔╝  ██╔════╝  ████╗░██║  ╚════██║
░░███╔═╝  █████╗  █████═╝░  █████╗░░  ██╔██╗██║  ░░░░██╔╝
██╔══╝░░  ╚════╝  ██╔═██╗░  ██╔══╝░░  ██║╚████║  ░░░██╔╝░
███████╗  ░░░░░░  ██║░╚██╗  ███████╗  ██║░╚███║  ░░██╔╝░░
╚══════╝  ░░░░░░  ╚═╝░░╚═╝  ╚══════╝  ╚═╝░░╚══╝  ░░╚═╝░░░
    
*/
#include <bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(), (a).end()
#define INFI INT32_MAX
#define INFL INT64_MAX
#define endl '\n'
#define yn(flag) cout << ((flag) ? "YES" : "NO") << endl
typedef long long ll; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<vvi> vvvi; typedef vector<long long> vl; 
typedef vector<vl> vvl; typedef vector<vvl> vvvl; typedef vector<string> vs; typedef vector<vs> vvs;
typedef vector<bool> vb; typedef vector<vb> vvb; typedef pair<int, int> pii; typedef pair<ll, ll> pll;
typedef pair<ll, int> pli; typedef pair<int, ll> pil; typedef vector<pii> vpii; 
const int diri[8] = { -1, 0, 0, 1, -1, -1, 1, 1 }; const int dirj[8] = { 0, 1, -1, 0, -1, 1, -1, 1 };
template<typename T,typename V> ostream& operator<<(ostream &s,pair<T,V> t) {return s<<"{"<<t.first<<","<<t.second<<"}";}
template<typename T> ostream& operator<<(ostream &s,vector<T> t) {s << "[";for (int i = 0; i < t.size(); ++i) {s << t[i];
if (i != t.size() - 1) {s << ", ";}}s << "]";return s;}
template<typename T, typename V> ostream& operator<<(ostream &s,map<T, V> t) {s << "{";for (auto& a : t) {s << a << " ";} s << "}";return s;}
template<typename T> ostream& operator<<(ostream &s, set<T> t) {s << "{";for (auto& a : t) {s << a << ", ";} s << "}";return s;}
template<typename... T> void put(T&&... args) { ((cout << args << " "), ...);}
template<typename... T> void putl(T&&... args) { ((cout << args << " "), ...); cout<<'\n';}
template<typename T> void input(vector<T>& t) { for (auto& v : t) cin >> v; }
auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
std::mt19937 mt(seed);
const int mod = 1e9+7;

const int inf = 1000000000;

int n;
vector<vector<int>> capacity, flow;
vector<int> excess;
vector<int> height, seen;
queue<int> excess_vertices;

void push(int u, int v)
{
    int d = min(excess[u], capacity[u][v] - flow[u][v]);
    flow[u][v] += d;
    flow[v][u] -= d;
    excess[u] -= d;
    excess[v] += d;
    if (d && excess[v] == d)
        excess_vertices.push(v);
}

void relabel(int u)
{
    int d = inf;
    for (int i = 0; i < n; i++) {
        if (capacity[u][i] - flow[u][i] > 0)
            d = min(d, height[i]);
    }
    if (d < inf)
        height[u] = d + 1;
}

void discharge(int u)
{
   while (excess[u] > 0) {
      if (seen[u] < n) {
         int v = seen[u];
         if (capacity[u][v] - flow[u][v] > 0 && height[u] > height[v])
            push(u, v);
         else 
            seen[u]++;
      } else {
         relabel(u);
         seen[u] = 0;
      }
   }
}

int max_flow(int s, int t)
{
   height.assign(n, 0);
   height[s] = n;
   flow.assign(n, vector<int>(n, 0.0));
   excess.assign(n, 0);
   excess[s] = inf;
   for (int i = 0; i < n; i++) {
      if (i != s)
         push(s, i);
   }
   seen.assign(n, 0);

   while (!excess_vertices.empty()) {
      int u = excess_vertices.front();
      excess_vertices.pop();
      if (u != s && u != t)
        discharge(u);
   }

   int max_flow = 0;
   for (int i = 0; i < n; i++)
      max_flow += flow[i][t];
   return max_flow;
}

const int N = 11;
bool dp[N][N][N][N], infected[N][N];
int main() {
   ios_base::sync_with_stdio(false);
   cin.tie(NULL); cout.tie(NULL);
   int t; cin >> n >> t;
   vector<string> scis(n), labs(n);
	input(scis);
	input(labs);
   auto get_sci = [&](int i, int j) {
      return i * n + j;
   };
   auto get_lab = [&](int i, int j) {
		return n * n + i * n + j;
   };
	int start = 2 * n * n;
	int end = start + 1;
	capacity.resize(end + 1, vector<int>(end + 1));
	int zi, zj;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (scis[i][j] == 'Z') {
				zi = i;
				zj = j;
			}
		}
	}
	vector<vector<int>> time(n, vector<int>(n, 1e9));
	queue<pair<int, int>> q;
	time[zi][zj] = 0;
	q.push({zi, zj});
	while (!q.empty()) {
		int curi = q.front().first;
		int curj = q.front().second;
		q.pop();
		for (int a = 0; a < 4; ++a) {
			int nexti = curi + diri[a];
			int nextj = curj + dirj[a];
			if (nexti < 0 || nextj < 0) continue;
			if (nexti >= n || nextj >= n) continue;
			if (!isdigit(scis[nexti][nextj])) continue;
			if (time[nexti][nextj] != 1e9) continue;
			time[nexti][nextj] = time[curi][curj] + 1;
			q.push({nexti, nextj});
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (isdigit(scis[i][j])) {
				capacity[start][get_sci(i, j)] = scis[i][j] - '0';
				capacity[get_lab(i, j)][end] = labs[i][j] - '0';
				vector<vector<int>> vis(n, vector<int>(n, -1));
				vis[i][j] = 0;
				q.push({i, j});
				while (!q.empty()) {
					int curi = q.front().first;
					int curj = q.front().second;
					q.pop();
					if (vis[curi][curj] <= min(time[curi][curj], t)) {
						capacity[get_sci(i, j)][get_lab(curi, curj)] = 1e9;
						if (vis[curi][curj] == min(time[curi][curj], t)) {
							continue;
						}
					}
					for (int a = 0; a < 4; ++a) {
						int nexti = curi + diri[a];
						int nextj = curj + dirj[a];
						if (nexti < 0 || nextj < 0) continue;
						if (nexti >= n || nextj >= n) continue;
						if (!isdigit(scis[nexti][nextj])) continue;
						if (vis[nexti][nextj] != -1) continue;
						vis[nexti][nextj] = vis[curi][curj] + 1;
						q.push({nexti, nextj});
					}
				}
			}
		}
	}
	n = end + 1;
	int res = max_flow(start, end);
	cout << res << endl;
   return 0;
}

/* Try this if you are stuck:
1) Maybe binary search on answer?
2) Try solving it in reverse
3) Think of a simple problem 
4) Think of elements which are special
   (like minimum, maximum, deepest node in tree, root)
5) Is it graph problem?
*/
/* DONT FORGET:
   EDGE CASES!!!!!
   N = 1,2...
   LONG LONG INSTEAD OF INT??
*/