Submission #306233
Source Code Expand
#include <algorithm>
#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>
namespace lc {
template <class WeightType, class CapacityType>
struct EdgeWithWeightAndCapacity {
int to;
WeightType weight;
CapacityType capacity;
EdgeWithWeightAndCapacity() : to(0), weight(), capacity() { }
EdgeWithWeightAndCapacity(
int to, const WeightType &weight, const CapacityType &capacity)
: to(to), weight(weight), capacity(capacity)
{ }
};
}
namespace lc {
template <typename EdgeType>
class AdjacencyList {
public:
typedef std::vector<EdgeType> ListType;
private:
std::vector<ListType> m_lists;
public:
explicit AdjacencyList(int n = 0)
: m_lists(n)
{ }
int size() const { return m_lists.size(); }
template <typename... Args>
void add_edge(int u, Args&&... args){
m_lists[u].emplace_back(args...);
}
const ListType &operator[](int u) const { return m_lists[u]; }
ListType &operator[](int u){ return m_lists[u]; }
};
}
namespace lc {
template <class EdgeType>
struct ResidualEdge : public EdgeType {
typedef ResidualEdge<EdgeType> self_type;
int rev;
ResidualEdge() : EdgeType(), rev(0) { }
template <class... Args>
ResidualEdge(int rev, Args&&... args)
: EdgeType(args...)
, rev(rev)
{ }
explicit ResidualEdge(const EdgeType &e)
: EdgeType(e)
, rev(0)
{ }
};
template <class EdgeType>
class ResidualAdjacencyList
: public AdjacencyList<ResidualEdge<EdgeType>>
{
public:
explicit ResidualAdjacencyList(int n = 0)
: AdjacencyList<ResidualEdge<EdgeType>>(n)
{ }
};
template <class EdgeType>
auto make_residual(const AdjacencyList<EdgeType> &graph)
-> ResidualAdjacencyList<EdgeType>
{
typedef decltype(EdgeType().capacity) capacity_type;
const int n = graph.size();
ResidualAdjacencyList<EdgeType> result(n);
for(int u = 0; u < n; ++u){
for(const auto &e : graph[u]){
const int v = e.to;
const int rev_u = result[v].size();
const int rev_v = result[u].size();
result[u].emplace_back(rev_u, e);
result[v].emplace_back(rev_v, e);
result[v].back().to = u;
result[v].back().capacity = capacity_type();
result[v].back().weight = -e.weight;
}
}
return result;
}
}
namespace lc {
template <class EdgeType>
auto mincostflow_primal_dual(
int source, int sink, decltype(EdgeType().capacity) flow,
ResidualAdjacencyList<EdgeType> &graph)
-> decltype(EdgeType().weight)
{
typedef decltype(EdgeType().weight) weight_type;
typedef decltype(EdgeType().capacity) capacity_type;
typedef std::pair<weight_type, int> weighted_pair;
const weight_type inf = std::numeric_limits<weight_type>::max();
const int n = graph.size();
weight_type result = 0;
std::vector<weight_type> h(n);
std::vector<int> prev_vertex(n), prev_edge(n);
while(flow > 0){
std::priority_queue<
weighted_pair, std::vector<weighted_pair>,
std::greater<weighted_pair>> pq;
std::vector<weight_type> dist(n, inf);
dist[source] = weight_type();
pq.push(std::make_pair(dist[source], source));
while(!pq.empty()){
weighted_pair p = pq.top();
pq.pop();
const int u = p.second;
if(dist[u] < p.first){ continue; }
for(size_t i = 0; i < graph[u].size(); ++i){
const auto &e = graph[u][i];
if(e.capacity <= 0){ continue; }
const int v = e.to;
const auto new_dist = dist[u] + e.weight + h[u] - h[v];
if(dist[v] <= new_dist){ continue; }
dist[v] = new_dist;
prev_vertex[v] = u;
prev_edge[v] = i;
pq.push(std::make_pair(new_dist, v));
}
}
if(dist[sink] >= inf){ return -1; }
for(int i = 0; i < n; ++i){ h[i] += dist[i]; }
weight_type diff = flow;
for(int v = sink; v != source; v = prev_vertex[v]){
diff = std::min(
diff, graph[prev_vertex[v]][prev_edge[v]].capacity);
}
flow -= diff;
result += diff * h[sink];
for(int v = sink; v != source; v = prev_vertex[v]){
auto &e = graph[prev_vertex[v]][prev_edge[v]];
e.capacity -= diff;
graph[v][e.rev].capacity += diff;
}
}
return result;
}
}
using namespace std;
typedef lc::EdgeWithWeightAndCapacity<int, int> Edge;
typedef pair<int, int> pii;
static const int dx[] = { 1, 0, -1, 0 };
static const int dy[] = { 0, -1, 0, 1 };
static const int INF = 1000000000;
inline bool between(int a, int b, int c){
return a <= b && b < c;
}
template <class EdgeType>
void solve(
vector<string> &field, int s, int c,
const lc::AdjacencyList<EdgeType> &graph)
{
const int n = graph.size();
const int h = field.size(), w = field[0].size();
while(s < n - 2){
bool flag = false;
if(s >= w * h){
s -= w * h;
flag = true;
}else{
for(const auto &e : graph[s]){
if(e.to >= n - 2){ continue; }
if(e.to == s + w * h){ continue; }
if(graph[e.to][e.rev].capacity == 0){
s = e.to;
flag = true;
break;
}
}
}
if(!flag){ break; }
const int y = s / w % h, x = s % w;
if(field[y][x] == '.'){ field[y][x] = c; }
}
}
int main(){
ios_base::sync_with_stdio(false);
int h, w;
cin >> h >> w;
vector<string> field(h);
for(int i = 0; i < h; ++i){ cin >> field[i]; }
const int num_vertices = h * w * 2 + 2;
const int source = num_vertices - 2, sink = num_vertices - 1;
int start = 0, goal_a = 0, goal_b = 0;
lc::AdjacencyList<Edge> graph(num_vertices);
for(int i = 0; i < h; ++i){
for(int j = 0; j < w; ++j){
const int x = i * w + j, y = x + w * h;
if(field[i][j] == '#'){ continue; }
graph.add_edge(x, y, 1, 1);
if(field[i][j] == 'S'){
start = x;
graph.add_edge(source, y, 0, 2);
}else if(field[i][j] == 'A'){
goal_a = x;
graph.add_edge(y, sink, 0, 1);
}else if(field[i][j] == 'B'){
goal_b = x;
graph.add_edge(y, sink, 0, 1);
}
for(int d = 0; d < 4; ++d){
const int nx = j + dx[d], ny = i + dy[d];
if(!between(0, nx, w) || !between(0, ny, h)){ continue; }
if(field[ny][nx] == 'O'){ continue; }
graph.add_edge(y, nx + ny * w, 0, 1);
}
}
}
vector< vector<int> > dist(h, vector<int>(w, INF));
queue<pii> q;
q.push(pii(start / w, start % w));
dist[start / w][start % w] = 0;
while(!q.empty()){
const pii p = q.front();
q.pop();
for(int d = 0; d < 4; ++d){
const int nx = p.second + dx[d], ny = p.first + dy[d];
if(!between(0, nx, w) || !between(0, ny, h)){ continue; }
if(field[ny][nx] == '#'){ continue; }
if(dist[ny][nx] >= INF){
dist[ny][nx] = dist[p.first][p.second] + 1;
q.push(pii(ny, nx));
}
}
}
auto residual = lc::make_residual(graph);
const int cost = lc::mincostflow_primal_dual(source, sink, 2, residual);
if(cost < 0 || cost > dist[goal_a / w][goal_a % w] + dist[goal_b / w][goal_b % w]){
cout << "NA" << endl;
return 0;
}
solve(field, goal_a, 'a', residual);
solve(field, goal_b, 'b', residual);
for(int i = 0; i < h; ++i){ cout << field[i] << endl; }
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Maze |
User |
logicmachine |
Language |
C++11 (GCC 4.8.1) |
Score |
100 |
Code Size |
7043 Byte |
Status |
AC |
Exec Time |
33 ms |
Memory |
2204 KB |
Judge Result
Set Name |
all |
Score / Max Score |
100 / 100 |
Status |
|
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 |
928 KB |
manual_j10.txt |
AC |
23 ms |
928 KB |
manual_j11.txt |
AC |
31 ms |
1956 KB |
manual_j12.txt |
AC |
23 ms |
800 KB |
manual_j13.txt |
AC |
23 ms |
804 KB |
manual_j14.txt |
AC |
24 ms |
748 KB |
manual_j15.txt |
AC |
23 ms |
928 KB |
manual_j2.txt |
AC |
28 ms |
1692 KB |
manual_j3.txt |
AC |
22 ms |
928 KB |
manual_j4.txt |
AC |
23 ms |
844 KB |
manual_j5.txt |
AC |
23 ms |
800 KB |
manual_j6.txt |
AC |
24 ms |
932 KB |
manual_j7.txt |
AC |
22 ms |
924 KB |
manual_j8.txt |
AC |
22 ms |
928 KB |
manual_j9.txt |
AC |
22 ms |
920 KB |
manual_k1.txt |
AC |
29 ms |
1952 KB |
manual_k2.txt |
AC |
30 ms |
2080 KB |
random_01.txt |
AC |
29 ms |
1836 KB |
random_02.txt |
AC |
29 ms |
1700 KB |
random_03.txt |
AC |
29 ms |
1700 KB |
random_04.txt |
AC |
29 ms |
1692 KB |
random_05.txt |
AC |
28 ms |
1432 KB |
random_06.txt |
AC |
27 ms |
1436 KB |
random_max_01.txt |
AC |
30 ms |
1956 KB |
random_max_02.txt |
AC |
30 ms |
1964 KB |
random_max_03.txt |
AC |
30 ms |
2076 KB |
random_max_04.txt |
AC |
29 ms |
1952 KB |
random_max_05.txt |
AC |
31 ms |
1884 KB |
random_max_06.txt |
AC |
30 ms |
1956 KB |
random_max_07.txt |
AC |
30 ms |
1956 KB |
random_max_08.txt |
AC |
28 ms |
1692 KB |
random_max_09.txt |
AC |
29 ms |
1696 KB |
random_max_10.txt |
AC |
29 ms |
1824 KB |
sample_01.txt |
AC |
24 ms |
800 KB |
sample_02.txt |
AC |
22 ms |
924 KB |
sample_03.txt |
AC |
22 ms |
928 KB |
sample_04.txt |
AC |
24 ms |
928 KB |
white_01.txt |
AC |
31 ms |
2012 KB |
white_02.txt |
AC |
33 ms |
2204 KB |
white_03.txt |
AC |
31 ms |
2084 KB |
white_04.txt |
AC |
29 ms |
1960 KB |