Submission #527705
Source Code Expand
/*{{{*/
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <functional>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
typedef int8_t sbyte;
typedef uint8_t byte;
typedef uint16_t ushort;
typedef uint32_t uint;
typedef int64_t i64;
typedef uint64_t u64;
template<class T> static inline T ABS(T x) {return x < 0 ? -x : x;}
template<class T> static inline void MAZ(T &a, const T &b) {if(a < b) a = b;}
template<class T> static inline void MIZ(T &a, const T &b) {if(b < a) a = b;}
/*}}}*/
static const int HMAX = 50;
static const int WMAX = 50;
static const int VMAX = 2 + HMAX * WMAX * 2;
static const int dir[4][2] = {{-1, 0}, {0, -1}, {0, +1}, {+1, 0}};
namespace Network
{
typedef int w_t;
static const w_t INF = 1000000;
struct EDGE
{
int v; w_t c,cc; int i;
EDGE(int v,w_t c,int i):v(v),c(c),cc(c),i(i) {}
};
int V,S,T;//TODO
vector<EDGE> f[VMAX];
int d[VMAX];
static int i[VMAX];
static w_t push(int u,w_t r)
{
if(u==T)return r;
const w_t o=r;
for(;i[u]!=f[u].size();i[u]++)
{
if(f[u][i[u]].c==0)continue;
const int v=f[u][i[u]].v;
if(d[v]!=d[u]+1||i[v]==f[v].size())continue;
const w_t w=push(v,min(r,f[u][i[u]].c));
if(w==0)continue;
f[u][i[u]].c-=w;
f[v][f[u][i[u]].i].c+=w;
if((r-=w)==0)break;
}
return o-r;
}
static bool bfs()
{
int qh=0,qt=0;
memset(d,0xFF,V*sizeof(int));
d[S]=0;i[qt++]=S;
do
{
const int u=i[qh++];
vector<EDGE>::const_iterator it;
for(it=f[u].begin();it!=f[u].end();++it)
{
if(it->c==0||d[it->v]>=0)continue;
d[it->v]=d[u]+1;
if(it->v==T)return true;
i[qt++]=it->v;
}
} while(qh!=qt);
return false;
}
w_t flow()
{
w_t ret=0;
while(bfs())
{
memset(i,0x00,V*sizeof(int));
ret+=push(S,INF);
}
return ret;
}
inline void insert(int a,int b,w_t cab,w_t cba)
{
if(b==a)return;
f[a].push_back(EDGE(b,cab,f[b].size() ));
f[b].push_back(EDGE(a,cba,f[a].size()-1));
}
void clear()
{
for(int i=0;i<V;i++)vector<EDGE>().swap(f[i]);
}
}
typedef pair<int, int> PII;
static int H, W;
static char M[HMAX][WMAX + 1];
static PII SP, AP, BP;
static int D[HMAX][WMAX];
static inline int ivertex(int i, int j) {
return 2 + ((i * W + j) << 1);
}
static inline int overtex(int i, int j) {
return ivertex(i, j) + 1;
}
static void trace(int u, char c) {
if(u == 0) return;
if(u >= 2) {
auto k = u - 2 >> 1;
auto i = k / W;
auto j = k % W;
if(i == AP.first && j == AP.second) {
c = 'a';
} else if(i == BP.first && j == BP.second) {
c = 'b';
} else if(i != SP.first || j != SP.second) {
M[i][j] = c;
}
}
for(auto &e : Network::f[u]) {
if(e.cc < e.c) {
trace(e.v, c);
if(u != 1) break;
}
}
}
static void solve() {
if(Network::flow() != 2) {
puts("NA");
} else {
trace(1, '?');
for(auto i = 0; i < H; i++) {
puts(M[i]);
}
}
Network::clear();
}
static void bfs() {
static deque<PII> q;
memset(D, 0xFF, sizeof(D));
D[SP.first][SP.second] = 0;
q.push_back(SP);
do {
auto u = q.front();
q.pop_front();
auto nd = D[u.first][u.second] + 1;
for(auto k = 0; k < 4; k++) {
auto i = u.first + dir[k][0];
if(i < 0 || i >= H) continue;
auto j = u.second + dir[k][1];
if(j < 0 || j >= W) continue;
if(M[i][j] == '#' || D[i][j] >= 0) continue;
D[i][j] = nd;
q.emplace_back(i, j);
}
} while(!q.empty());
}
static void build() {
bfs();
Network::V = 2 + H * W * 2;
Network::S = 0;
Network::T = 1;
for(auto i = 0; i < H; i++) {
for(auto j = 0; j < W; j++) {
if(D[i][j] < 0) continue;
if(M[i][j] == 'S') {
Network::insert(0, ivertex(i, j), 2, 0);
Network::insert(ivertex(i, j), overtex(i, j), 2, 0);
} else {
Network::insert(ivertex(i, j), overtex(i, j), 1, 0);
}
if(M[i][j] == 'A' || M[i][j] == 'B') {
Network::insert(overtex(i, j), 1, 1, 0);
continue;
}
for(auto k = 0; k < 4; k++) {
auto ii = i + dir[k][0];
if(ii < 0 || ii >= H) continue;
auto jj = j + dir[k][1];
if(jj < 0 || jj >= W) continue;
if(D[ii][jj] != D[i][j] + 1) continue;
Network::insert(overtex(i, j), ivertex(ii, jj), 1, 0);
}
}
}
}
static void input() {
scanf("%d%d", &H, &W);
for(auto i = 0; i < H; i++) {
scanf(" ");
for(auto j = 0; j < W; j++) {
M[i][j] = getchar();
if(M[i][j] == 'S') {
SP = PII(i, j);
} else if(M[i][j] == 'A') {
AP = PII(i, j);
} else if(M[i][j] == 'B') {
BP = PII(i, j);
}
}
}
}
int main() {
input();
build();
solve();
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Maze |
User |
arosusti |
Language |
C++11 (GCC 4.8.1) |
Score |
100 |
Code Size |
5051 Byte |
Status |
AC |
Exec Time |
31 ms |
Memory |
1560 KB |
Compile Error
./Main.cpp: In function ‘void input()’:
./Main.cpp:222:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &H, &W);
^
./Main.cpp:224:13: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf(" ");
^
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 |
27 ms |
992 KB |
manual_j10.txt |
AC |
27 ms |
1000 KB |
manual_j11.txt |
AC |
28 ms |
1460 KB |
manual_j12.txt |
AC |
25 ms |
1080 KB |
manual_j13.txt |
AC |
27 ms |
1076 KB |
manual_j14.txt |
AC |
26 ms |
1076 KB |
manual_j15.txt |
AC |
25 ms |
1172 KB |
manual_j2.txt |
AC |
28 ms |
1436 KB |
manual_j3.txt |
AC |
26 ms |
1176 KB |
manual_j4.txt |
AC |
28 ms |
1176 KB |
manual_j5.txt |
AC |
27 ms |
1076 KB |
manual_j6.txt |
AC |
26 ms |
1080 KB |
manual_j7.txt |
AC |
28 ms |
1072 KB |
manual_j8.txt |
AC |
26 ms |
1172 KB |
manual_j9.txt |
AC |
27 ms |
1172 KB |
manual_k1.txt |
AC |
30 ms |
1384 KB |
manual_k2.txt |
AC |
29 ms |
1376 KB |
random_01.txt |
AC |
28 ms |
1376 KB |
random_02.txt |
AC |
29 ms |
1336 KB |
random_03.txt |
AC |
28 ms |
1240 KB |
random_04.txt |
AC |
28 ms |
1204 KB |
random_05.txt |
AC |
28 ms |
1352 KB |
random_06.txt |
AC |
28 ms |
1304 KB |
random_max_01.txt |
AC |
29 ms |
1464 KB |
random_max_02.txt |
AC |
31 ms |
1464 KB |
random_max_03.txt |
AC |
30 ms |
1372 KB |
random_max_04.txt |
AC |
30 ms |
1376 KB |
random_max_05.txt |
AC |
29 ms |
1436 KB |
random_max_06.txt |
AC |
28 ms |
1428 KB |
random_max_07.txt |
AC |
28 ms |
1332 KB |
random_max_08.txt |
AC |
28 ms |
1336 KB |
random_max_09.txt |
AC |
28 ms |
1300 KB |
random_max_10.txt |
AC |
28 ms |
1204 KB |
sample_01.txt |
AC |
25 ms |
1076 KB |
sample_02.txt |
AC |
27 ms |
1172 KB |
sample_03.txt |
AC |
28 ms |
988 KB |
sample_04.txt |
AC |
27 ms |
1156 KB |
white_01.txt |
AC |
31 ms |
1512 KB |
white_02.txt |
AC |
31 ms |
1440 KB |
white_03.txt |
AC |
28 ms |
1560 KB |
white_04.txt |
AC |
29 ms |
1464 KB |