Submission #306143


Source Code Expand

#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_DEPRECATE

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>
#include <fstream>
#include <iterator>
#include <bitset>

using namespace std;

typedef long long ll;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;

#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)(c).size())
#define ten(x) ((int)1e##x)

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
typedef unsigned long long ull;

struct Edge {
	int cap; // capacity
	int to;
	int rev; // reverse edge id

	Edge() {}
	Edge(int c, int t, int r) :
		cap(c), to(t), rev(r) {
	}
};

struct CostEdge : public Edge {
	int cost;
	CostEdge() : Edge() {}
	CostEdge(int c, int t, int cs, int r) :
		Edge(c, t, r), cost(cs) {
	}
};

template<class E> // Edge type
class Graph {
public:
	typedef std::vector<std::vector<E> > G;

private:
	G g;

public:
	Graph(int n) : g(G(n)) {}

	void addEdge(int from, int to, int cap, int cost) {
		g[from].push_back(E(cap, to, cost, g[to].size()));
		g[to].push_back(E(0, from, -cost, g[from].size() - 1)); //rev edge
	}

	G &getRowGraph() {
		return g;
	}
};

// O(VE+FElogV)
template<class E>
int minCostFlow(Graph<E> &graph, int s, int t, int f, bool negative = false) {
	typedef pair<int, int> P;
	typename Graph<E>::G &g = graph.getRowGraph();
	int n = g.size();
	int res = 0;
	vector<int> h(n, 0);
	vector<int> prevv(n);
	vector<int> preve(n);
	const int inf = 10000000; //check

	//負の辺に対応?
	if (negative) {
		vector<int> dist(n, inf);
		dist[s] = 0;

		bool update = true;

		while (update) {
			update = false;
			for (int v = 0; v < n; v++) {
				if (dist[v] == inf) continue;
				for (int i = 0; i < (int)g[v].size(); i++) {
					E &e = g[v][i];
					if (e.cap > 0 && dist[e.to] > dist[v] + e.cost) {
						dist[e.to] = dist[v] + e.cost;
						prevv[e.to] = v;
						preve[e.to] = i;
						update = true;
					}
				}
			}
		}

		for (int i = 0; i < n; i++)
			h[i] = dist[i];
	}

	while (f > 0) {
		//ダイクストラで最短経路(cost = 辺の費用)
		priority_queue<P, vector<P>, greater<P> > que;
		vector<int> dist(n, inf);
		dist[s] = 0;
		que.push(P(0, s));

		while (!que.empty()) {
			P p = que.top(); que.pop();
			int v = p.second;
			if (dist[v] < p.first) continue;
			for (int i = 0; i < (int)g[v].size(); i++) {
				E &e = g[v][i];

				if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
					dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
					prevv[e.to] = v;
					preve[e.to] = i;
					que.push(P(dist[e.to], e.to));
				}
			}
		}

		if (dist[t] == inf) {
			return -1; //最短経路なし
		}

		for (int v = 0; v < n; v++) h[v] += dist[v];

		//s-t間に目一杯流す
		int d = f;
		for (int v = t; v != s; v = prevv[v]) {
			d = min(d, g[prevv[v]][preve[v]].cap);
		}

		f -= d;//流した分を引く
		res += d * h[t]; //流した分からコストの計算をする

		//逆辺の計算
		for (int v = t; v != s; v = prevv[v]) {
			E &e = g[prevv[v]][preve[v]];
			e.cap -= d;
			g[v][e.rev].cap += d;
		}
	}
	return res;
}

#define ID(a,b) (a*w+b)

char board[50][51];

int main(){
	int h, w; cin >> h >> w;
	FOR(i, h) cin >> board[i];

	const int n = 2 + 2 * h*w;
	int a, b, s;
	FOR(i, h) FOR(j, w) {
		if (board[i][j] == 'A') a = ID(i, j);
		if (board[i][j] == 'B') b = ID(i, j);
		if (board[i][j] == 'S') s = ID(i, j);
	}

	Graph<CostEdge> g(n);
	FOR(i, h) FOR(j, w) {
		if (board[i][j] == '#') continue;
		const int dx[] = { 0, 1, 0, -1 };
		const int dy[] = { 1, 0, -1, 0 };
		int id = ID(i, j);
		FOR(k, 4) {
			int ni = i + dx[k];
			int nj = j + dy[k];
			if (0 <= ni && ni < h && 0 <= nj && nj < w && board[ni][nj] != '#') {
				int nid = ID(ni, nj);
				g.addEdge(id * 2 + 1, nid * 2, 1,1);
			}
		}
	}

	FOR(i, h) FOR(j, w) {
		if (board[i][j] == '#') continue;
		int id = ID(i, j);
		int cap = (id == s) ? 2 : 1;
		g.addEdge(id * 2, id * 2 + 1 , cap, 0);
	}

	const int src = n - 2, dst = n - 1;
	g.addEdge(src, s * 2, 2, 0);

	auto g2 = g;
	g2.addEdge(a * 2 + 1, dst, 1 , 0);
	int s2a = minCostFlow(g2, src, dst, 1);
	
	auto g3 = g;
	g3.addEdge(b * 2 + 1, dst, 1 , 0);
	int s2b = minCostFlow(g3, src, dst, 1);

	g.addEdge(a * 2 + 1, dst, 1, 0);
	g.addEdge(b * 2 + 1, dst, 1, 0);
	int s2ab = minCostFlow(g, src, dst, 2);

	if (s2ab != s2a + s2b) {
		puts("NA");
	} else {
		{
			int cur = 2 * a;
			auto rG = g.getRowGraph();
			while (cur != 2 * s) {
				for (auto e : rG[cur]) {
					if (e.cost == -1 && e.cap == 1) {
						int from = e.to;
						cur = from - 1;
						int i = cur / 2 / w;
						int j = cur / 2 % w;
						board[i][j] = 'a';
						//fprintf(stderr,"%d %d\n",i,j);
						break;
					}
				}
			}
		}
		{
			int cur = 2 * b;
			auto rG = g.getRowGraph();
			while (cur != 2 * s) {
				for (auto e : rG[cur]) {
					if (e.cost == -1 && e.cap == 1) {
						int from = e.to;
						cur = from - 1;
						int i = cur / 2 / w;
						int j = cur / 2 % w;
						//fprintf(stderr, "%d %d\n", i, j);
						board[i][j] = 'b';
						break;
					}
				}
			}
		}
		board[s / w][s%w] = 'S';
		FOR(i, h) puts(board[i]);
	}
}

Submission Info

Submission Time
Task D - Maze
User math
Language C++11 (GCC 4.8.1)
Score 100
Code Size 5801 Byte
Status AC
Exec Time 39 ms
Memory 3352 KB

Judge Result

Set Name all
Score / Max Score 100 / 100
Status
AC × 41
Set Name Test Cases
all manual_j1.txt, manual_j10.txt, manual_j11.txt, manual_j12.txt, manual_j13.txt, manual_j14.txt, manual_j15.txt, manual_j2.txt, manual_j3.txt, manual_j4.txt, manual_j5.txt, manual_j6.txt, manual_j7.txt, manual_j8.txt, manual_j9.txt, manual_k1.txt, manual_k2.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_max_01.txt, random_max_02.txt, random_max_03.txt, random_max_04.txt, random_max_05.txt, random_max_06.txt, random_max_07.txt, random_max_08.txt, random_max_09.txt, random_max_10.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, white_01.txt, white_02.txt, white_03.txt, white_04.txt
Case Name Status Exec Time Memory
manual_j1.txt AC 27 ms 856 KB
manual_j10.txt AC 27 ms 856 KB
manual_j11.txt AC 37 ms 3348 KB
manual_j12.txt AC 24 ms 928 KB
manual_j13.txt AC 25 ms 964 KB
manual_j14.txt AC 24 ms 924 KB
manual_j15.txt AC 26 ms 1052 KB
manual_j2.txt AC 31 ms 2140 KB
manual_j3.txt AC 23 ms 924 KB
manual_j4.txt AC 30 ms 836 KB
manual_j5.txt AC 26 ms 852 KB
manual_j6.txt AC 28 ms 864 KB
manual_j7.txt AC 25 ms 860 KB
manual_j8.txt AC 25 ms 924 KB
manual_j9.txt AC 25 ms 928 KB
manual_k1.txt AC 37 ms 3032 KB
manual_k2.txt AC 39 ms 2648 KB
random_01.txt AC 34 ms 2260 KB
random_02.txt AC 37 ms 2396 KB
random_03.txt AC 32 ms 2092 KB
random_04.txt AC 32 ms 2136 KB
random_05.txt AC 33 ms 1944 KB
random_06.txt AC 31 ms 1624 KB
random_max_01.txt AC 38 ms 3344 KB
random_max_02.txt AC 38 ms 3164 KB
random_max_03.txt AC 34 ms 2648 KB
random_max_04.txt AC 38 ms 2984 KB
random_max_05.txt AC 39 ms 2824 KB
random_max_06.txt AC 35 ms 2648 KB
random_max_07.txt AC 35 ms 2524 KB
random_max_08.txt AC 32 ms 2396 KB
random_max_09.txt AC 30 ms 2012 KB
random_max_10.txt AC 29 ms 2008 KB
sample_01.txt AC 26 ms 856 KB
sample_02.txt AC 23 ms 924 KB
sample_03.txt AC 24 ms 856 KB
sample_04.txt AC 27 ms 856 KB
white_01.txt AC 39 ms 3352 KB
white_02.txt AC 37 ms 3352 KB
white_03.txt AC 39 ms 3348 KB
white_04.txt AC 35 ms 2904 KB