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

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