Submission #306293


Source Code Expand

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <cstring>
using namespace std;
/********************************************/
#define N 18000
#define inf 2000000000
#define Min(a,b) (((a)<(b))?a:b)
struct edge {
	int s, t, f, v, next;
} e[10 * N];
int eid;
int node[N];
void init() {
	memset(node, -1, sizeof(node));
	eid = 0;
}
void addedge(int s, int t, int f, int v) {
	e[eid].s = s;
	e[eid].t = t;
	e[eid].f = f;
	e[eid].v = v;
	e[eid].next = node[s];
	node[s] = eid++;
	e[eid].s = t;
	e[eid].t = s;
	e[eid].f = 0;
	e[eid].v = -v;
	e[eid].next = node[t];
	node[t] = eid++;
}
int dist[N], path[N];
bool in[N];
queue<int> q;
int SPFA(int s, int t, int n) {
	int i, u, v;
	memset(in, false, sizeof(in));
	for (i = 0; i < n; ++i)
		dist[i] = inf;
	dist[s] = 0;
	path[s] = -1;
	q.push(s);
	in[s] = true;
	while (!q.empty()) {
		u = q.front();
		q.pop();
		in[u] = false;
		for (i = node[u]; i != -1; i = e[i].next) {
			v = e[i].t;
			if (e[i].f > 0 && dist[u] + e[i].v < dist[v]) {
				dist[v] = dist[u] + e[i].v;
				path[v] = i;
				if (!in[v]) {
					q.push(v);
					in[v] = true;
				}
			}
		}
	}
	return dist[t] != inf;
}
void output() {
	int i;
	for (i = 0; i < eid; ++i)
		printf("s:%d t:%d f:%d v:%d next:%d\n", e[i].s, e[i].t, e[i].f, e[i].v,
				e[i].next);
}
int max_flow_min_cost(int s, int t, int n, int& cost) {
	int i, minf, f = 0;
	//output();
	while (SPFA(s, t, n)) {
		//printf("ok\n");
		for (i = path[t], minf = e[path[t]].f; i != -1; i = path[e[i].s]) {
			minf = Min(minf, e[i].f);
		}
		f += minf;
		for (i = path[t]; i != -1; i = path[e[i].s]) {
			cost += minf * e[i].v;
			e[i].f -= minf;
			e[i ^ 1].f += minf;
		}
	}
	return f;
}
/********************************************/

char s[55][55];
int dir[4][2] = { 0, 1, 1, 0, 0, -1, -1, 0 };

vector<int> nt[10005];

int main() {
	int n, m;
	int i, j, k;
	int S, T;
	scanf("%d%d", &n, &m);
	for (i = 0; i < n; ++i) {
		scanf("%s", s[i]);
	}
	int start, end1, end2;
	for (i = 0; i < n; ++i) {
		for (j = 0; j < m; ++j) {
			if (s[i][j] == 'S')
				start = i * m + j;
			if (s[i][j] == 'A')
				end1 = i * m + j;
			if (s[i][j] == 'B')
				end2 = i * m + j;
		}
	}
	////////////////1/////////////////////////
	init();
	for (i = 0; i < n; ++i) {
		for (j = 0; j < m; ++j) {
			if (s[i][j] == '#')
				continue;
			for (k = 0; k < 4; ++k) {
				int ii, jj;
				ii = i + dir[k][0];
				jj = j + dir[k][1];
				if (ii < 0 || jj < 0 || ii >= n || jj >= m)
					continue;
				if (s[ii][jj] == '#')
					continue;
				addedge(i * m + j, ii * m + jj, 1, 1);
			}
		}
	}
	S = n * m;
	T = S + 1;
	addedge(S, start, 2, 0);
	addedge(end1, T, 1, 0);
	int cost1;
	cost1 = 0;
	max_flow_min_cost(S, T, T + 1, cost1);

	///////////////////////2//////////////////////////
	init();
	for (i = 0; i < n; ++i) {
		for (j = 0; j < m; ++j) {
			if (s[i][j] == '#')
				continue;
			for (k = 0; k < 4; ++k) {
				int ii, jj;
				ii = i + dir[k][0];
				jj = j + dir[k][1];
				if (ii < 0 || jj < 0 || ii >= n || jj >= m)
					continue;
				if (s[ii][jj] == '#')
					continue;
				addedge(i * m + j, ii * m + jj, 1, 1);
			}
		}
	}
	S = n * m;
	T = S + 1;
	addedge(S, start, 2, 0);
	addedge(end2, T, 1, 0);
	int cost2;
	cost2 = 0;
	max_flow_min_cost(S, T, T + 1, cost2);
	///////////////////////3////////////////////////
	init();

	for (i = 0; i < n; ++i) {
		for (j = 0; j < m; ++j) {
			if (s[i][j] == '#')
				continue;
			addedge(i * m + j, n * m + i * m + j, 1, 0);
		}
	}
	addedge(start, n * m + start, 1, 0);
	for (i = 0; i < n; ++i) {
		for (j = 0; j < m; ++j) {
			if (s[i][j] == '#')
				continue;
			for (k = 0; k < 4; ++k) {
				int ii, jj;
				ii = i + dir[k][0];
				jj = j + dir[k][1];
				if (ii < 0 || jj < 0 || ii >= n || jj >= m)
					continue;
				if (s[ii][jj] == '#')
					continue;
				addedge(n * m + i * m + j, ii * m + jj, 1, 1);
			}
		}
	}

	S = 2 * n * m;
	T = S + 1;
	addedge(S, start, 2, 0);
	addedge(n * m + end1, T, 1, 0);
	addedge(n * m + end2, T, 1, 0);
	int cost, f;
	cost = 0;
	f = 0;
	f = max_flow_min_cost(S, T, T + 1, cost);
	///////////////////////////////////////////////////////
	if (f != 2) {
		printf("NA\n");
		return 0;
	}
	if (cost != cost1 + cost2) {
		printf("NA\n");
		return 0;
	}
	for (i = 0; i < eid; i += 2) {
		if (e[i].f != 0)
			continue;
		if (e[i].s != S && e[i].t != T) {
			if (e[i].s % (n * m) == e[i].t % (n * m))
				continue;
			nt[e[i].t % (n * m)].push_back(e[i].s % (n * m));
		}
	}
	int now = nt[end1][0];
	while (now != start) {
		s[now / m][now % m] = 'a';
		now = nt[now][0];
	}
	now = nt[end2][0];
	while (now != start) {
		s[now / m][now % m] = 'b';
		now = nt[now][0];
	}
	for (i = 0; i < n; ++i) {
		printf("%s\n", s[i]);
	}
	return 0;
}

Submission Info

Submission Time
Task D - Maze
User asian-2014-1511
Language C++ (G++ 4.6.4)
Score 100
Code Size 5217 Byte
Status AC
Exec Time 29 ms
Memory 1700 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:113:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:115:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

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 25 ms 1176 KB
manual_j10.txt AC 25 ms 1044 KB
manual_j11.txt AC 26 ms 1568 KB
manual_j12.txt AC 25 ms 1176 KB
manual_j13.txt AC 25 ms 1172 KB
manual_j14.txt AC 24 ms 1180 KB
manual_j15.txt AC 24 ms 1056 KB
manual_j2.txt AC 27 ms 1432 KB
manual_j3.txt AC 25 ms 1180 KB
manual_j4.txt AC 24 ms 1184 KB
manual_j5.txt AC 24 ms 1052 KB
manual_j6.txt AC 24 ms 1180 KB
manual_j7.txt AC 25 ms 1176 KB
manual_j8.txt AC 26 ms 1180 KB
manual_j9.txt AC 25 ms 1176 KB
manual_k1.txt AC 27 ms 1684 KB
manual_k2.txt AC 25 ms 1692 KB
random_01.txt AC 26 ms 1432 KB
random_02.txt AC 27 ms 1436 KB
random_03.txt AC 28 ms 1312 KB
random_04.txt AC 27 ms 1428 KB
random_05.txt AC 26 ms 1424 KB
random_06.txt AC 29 ms 1256 KB
random_max_01.txt AC 28 ms 1688 KB
random_max_02.txt AC 28 ms 1560 KB
random_max_03.txt AC 26 ms 1700 KB
random_max_04.txt AC 25 ms 1560 KB
random_max_05.txt AC 29 ms 1440 KB
random_max_06.txt AC 25 ms 1440 KB
random_max_07.txt AC 26 ms 1440 KB
random_max_08.txt AC 25 ms 1444 KB
random_max_09.txt AC 26 ms 1308 KB
random_max_10.txt AC 24 ms 1308 KB
sample_01.txt AC 24 ms 1184 KB
sample_02.txt AC 24 ms 1188 KB
sample_03.txt AC 24 ms 1100 KB
sample_04.txt AC 26 ms 1184 KB
white_01.txt AC 27 ms 1696 KB
white_02.txt AC 26 ms 1640 KB
white_03.txt AC 26 ms 1696 KB
white_04.txt AC 25 ms 1700 KB