Submission #306294

---

Source Code Expand

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<math.h>
using namespace std;
#define ll int
const int inf = 1e8;
#define Inf 0x3FFFFFFFFFFFFFFFLL  
const int N = 55 * 55 * 2;
const int M = N * 4;
struct Edge {
	ll to, cap, cost, nex;
	Edge(){}
	Edge(ll to, ll cap, ll cost, ll next) :to(to), cap(cap), cost(cost), nex(next){}
} edge[M << 1];
ll head[N], edgenum;
ll D[N], A[N], P[N];
bool inq[N];
void add(ll from, ll to, ll cap, ll cost) {
	edge[edgenum] = Edge(to, cap, cost, head[from]);
	head[from] = edgenum++;
	edge[edgenum] = Edge(from, 0, -cost, head[to]);
	head[to] = edgenum++;
}
bool spfa(ll s, ll t, ll &flow, ll &cost) {
	for (ll i = 0; i <= t; i++) D[i] = inf;
	memset(inq, 0, sizeof inq);
	queue<ll>q;
	q.push(s);
	D[s] = 0; A[s] = inf;
	while (!q.empty()) {
		ll u = q.front(); q.pop();
		inq[u] = 0;
		for (ll i = head[u]; ~i; i = edge[i].nex)
		{
			Edge &e = edge[i];
			if (e.cap && D[e.to] > D[u] + e.cost)
			{
				D[e.to] = D[u] + e.cost;
				P[e.to] = i;
				A[e.to] = min(A[u], e.cap);
				if (!inq[e.to])
				{
					inq[e.to] = 1; q.push(e.to);
				}
			}
		}
	}
	//若费用为inf则中止费用流
	if (D[t] == inf) return false;
	cost += D[t] * A[t];
	flow += A[t];
	ll u = t;
	while (u != s) {
		edge[P[u]].cap -= A[t];
		edge[P[u] ^ 1].cap += A[t];
		u = edge[P[u] ^ 1].to;
	}
	return true;
}
ll cost, flow;
ll Mincost(ll s, ll t){
	flow = 0; cost = 0;
	while (spfa(s, t, flow, cost));
	return flow;
}
void init(){ memset(head, -1, sizeof head); edgenum = 0; }

int n, m;
char mp[55][55];
int from = 0, to, step[4][2] = { 0, 1, 0, -1, 1, 0, -1, 0 };
int has(int x, int y){
	return (x - 1)*m + y;
}
int has2(int x, int y){
	return n*m + (x - 1)*m + y;
}
void dfs(vector<int>&G, int now, int fa){
	while (now != to){
		G.push_back(now);
		fa = now;
		now += n*m;
		for (int i = head[now]; ~i; i = edge[i].nex){
			if (edge[i].cap == 0 && edge[i].to != fa){
				now = edge[i].to;
				break;
			}
		}
	}
}
bool inmap(int x, int y){
	return 1 <= x && x <= n && 1 <= y&&y <= m;
}
vector<int>G[2];
struct node{
	int x, y;
	node(int a, int b) :x(a), y(b){}
	node(){};
}SS, AA, BB;
int Dis[55][55];
int dis(node aa, node bb){
	for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)Dis[i][j] = -1;
	queue<int>qx, qy;
	qx.push(aa.x); qy.push(aa.y);
	Dis[aa.x][aa.y] = 0;
	while (!qx.empty()){
		int ux = qx.front(); qx.pop();
		int uy = qy.front(); qy.pop();
		for (int i = 0; i < 4; i++){
			int vx = ux + step[i][0], vy = uy + step[i][1];
			if (inmap(vx, vy) && mp[vx][vy]!='#' && Dis[vx][vy] == -1){
				Dis[vx][vy] = Dis[ux][uy] + 1;
				if (vx == bb.x && vy == bb.y)return Dis[vx][vy];
				qx.push(vx);
				qy.push(vy);
			}
		}
	}
	return inf;
}
void input(){
	init();
	to = n*m * 2 + 1;
	for (int i = 1; i <= n; i++)
	{
		scanf("%s", mp[i] + 1);
		for (int j = 1; j <= m; j++)
		{
			if (mp[i][j] == '#')continue;
			else if (mp[i][j] == 'S')
				SS = node(i, j);
			else if (mp[i][j] == 'A'){
				AA = node(i, j);
				add(has2(i, j), to, 1, 0);
			}
			else if (mp[i][j] == 'B'){
				BB = node(i, j);
				add(has2(i, j), to, 1, 0);
			}
			if (mp[i][j] == 'S')
				add(has(i, j), has2(i, j), 2, 0);
			else
				add(has(i, j), has2(i, j), 1, 1);
			for (int k = 0; k < 4; k++)
			{
				int x = i + step[k][0], y = j + step[k][1];
				if (inmap(x, y) && mp[x][y] != '#')
					add(has2(i, j), has(x, y), 1, 0);
			}
		}
	}
}
void pt(vector<int>&D, char c){
	for (int i = 0; i < D.size()-1; i++){
		int x = D[i] / m, y = D[i] % m;
		if (D[i] % m == 0) y = m;
		else x++;
		mp[x][y] = c;
	}
}
bool equ(node p, int Y){
	int x = Y / m, y = Y % m;
	if (Y % m == 0) y = m;
	else x++;
	return p.x == x && p.y == y;
}
int main(){
	while (cin >> n >> m){
		input();
		int to2 = to + 1;
		add(to, to2, 2, 0);
		int all = dis(SS, AA) + dis(SS, BB); 
		if (all >= inf){
			puts("NA"); continue;
		}
		Mincost(has(SS.x, SS.y), to2);
		if (2 != flow || cost != all){
			puts("NA");
		}
		else {
			int cur = 0;
			G[0].clear(); G[1].clear();
			for (int i = head[has2(SS.x, SS.y)]; ~i; i = edge[i].nex)
				if (edge[i].cap == 0 && !equ(SS, edge[i].to))
				{
					dfs(G[cur], edge[i].to, has2(SS.x, SS.y));
					cur++;
				}
				if (G[1].size() && equ(AA, G[1][G[1].size() - 1]))swap(G[0], G[1]);
				if (G[0].size() && equ(BB, G[0][G[0].size() - 1]))swap(G[0], G[1]);
				if (G[0].size())
					pt(G[0], 'a');
				if (G[1].size())
					pt(G[1], 'b');
				
				for (int i = 1; i <= n; i++)
					printf("%s\n", mp[i] + 1);
		}
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void input()’:
./Main.cpp:127:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result