Submission #306875

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cstring>
#include <functional>
#include <cmath>
#include <utility>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define all(c) (c).begin(),(c).end()
#define fs first
#define sc second
#define pb push_back
#define show(x) cout << #x << " " << x << endl
typedef pair<int,int> P;
struct edge {int to,cap,cost,rev;};
const int MAX_V=10000,INF=1e8;
int V;
vector<edge> G[MAX_V];
int h[MAX_V];
int dist[MAX_V];
int prevv[MAX_V],preve[MAX_V];
void add_edge(int from, int to, int cap, int cost){
	edge e1={to,cap,cost,G[to].size()},e2={from,0,-cost,G[from].size()};
	G[from].push_back(e1);
	G[to].push_back(e2);
}
int min_cost_flow(int s, int t, int f){
	int res=0;
	fill(h,h+V,0);
	while(f>0){
		priority_queue< P,vector<P>,greater<P> > que;
		fill(dist,dist+V,INF);
		dist[s]=0;
		que.push(P(0,s));
		while(!que.empty()){
			P p=que.top();
			que.pop();
			int v=p.second;
			if(dist[v]<p.first) continue;
			for(int i=0;i<G[v].size();i++){
				edge &e=G[v][i];
				if(e.cap>0 && dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){
					dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];
					prevv[e.to]=v;
					preve[e.to]=i;
					que.push(P(dist[e.to],e.to));
				}
			}
		}
		if(dist[t]==INF) return -1;
		for(int v=0;v<V;v++) h[v]+=dist[v];
		int d=f;
		for(int v=t;v!=s;v=prevv[v]){
			d=min(d,G[prevv[v]][preve[v]].cap);
		}
		f-=d;
		res+=d*h[t];
		for(int v=t;v!=s;v=prevv[v]){
			edge &e=G[prevv[v]][preve[v]];
			e.cap-=d;
			G[v][e.rev].cap+=d;
		}
	}
	return res;
}
string s[50];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int H,W;
bool is(int x,int y){
	return 0<=x&&x<H&&0<=y&&y<W&&s[x][y]!='#';
}
int d[50][50];
void bfs(int sx,int sy){
	queue<P> que;
	que.push(P(sx,sy));
	rep(i,H) rep(j,W) d[i][j]=INF;
	d[sx][sy]=0;
	while(!que.empty()){
		P p=que.front();
		que.pop();
		int x=p.fs,y=p.sc;
		rep(di,4){
			int nx=x+dx[di],ny=y+dy[di];
			if(!is(nx,ny)) continue;
			if(d[nx][ny]!=INF) continue;
			d[nx][ny]=d[x][y]+1;
			que.push(P(nx,ny));
		}
	}
}
int in(int x,int y){
	return (x*W+y)*2;
}
int out(int x,int y){
	return (x*W+y)*2+1;
}
int main(){
	cin>>H>>W;
	rep(i,H) cin>>s[i];
	int sx,sy;
	rep(i,H) rep(j,W) if(s[i][j]=='S') sx=i,sy=j;
	bfs(sx,sy);
	rep(i,H) rep(j,W) rep(di,4){
		if(s[i][j]=='#') continue;
		int nx=i+dx[di],ny=j+dy[di];
		if(!is(nx,ny)) continue;
		add_edge(out(nx,ny),in(i,j),1,1);
	}
	rep(i,H) rep(j,W){
		int tt=1;
		if(s[i][j]=='S') tt=2;
		add_edge(in(i,j),out(i,j),tt,0);
	}
	int S=H*W*2,T=S+1;
	V=T+1;
	int ax,ay,bx,by;
	int da,db;
	rep(i,H) rep(j,W){
		if(s[i][j]=='S'){
			add_edge(S,in(i,j),2,0);
		}
		if(s[i][j]=='A'){
			add_edge(out(i,j),T,1,0);
			da=d[i][j];
			ax=i,ay=j;
		}
		if(s[i][j]=='B'){
			add_edge(out(i,j),T,1,0);
			db=d[i][j];
			bx=i,by=j;
		}
	}
//	show(da);
//	show(db);
	int f=da+db;
	if(f>=INF){
		puts("NA");
		return 0;
	}
	int t=min_cost_flow(S,T,2);
	if(t!=f){
		puts("NA");
		return 0;
	}
	int x=ax,y=ay;
	while(s[x][y]!='S'){
		for(auto e:G[in(x,y)]){
			if(e.to>=S) continue;
			if(e.cap==1){
				x=(e.to)/2/W,y=(e.to)/2%W;
				if(s[x][y]!='S') s[x][y]='a';
				break;
			}
		}
	}
	x=bx,y=by;
	while(s[x][y]!='S'){
		for(auto e:G[in(x,y)]){
			if(e.to>=S) continue;
			if(e.cap==1){
				x=(e.to)/2/W,y=(e.to)/2%W;
				if(s[x][y]!='S') s[x][y]='b';
				break;
			}
		}
	}
	rep(i,H) cout<<s[i]<<endl;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void add_edge(int, int, int, int)’:
./Main.cpp:31:34: warning: narrowing conversion of ‘G[to].std::vector<_Tp, _Alloc>::size<edge, std::allocator<edge> >()’ from ‘std::vector<edge>::size_type {aka long unsigned int}’ to ‘int’ inside { } [-Wnarrowing]
  edge e1={to,cap,cost,G[to].size()},e2={from,0,-cost,G[from].size()};
                                  ^
./Main.cpp:31:67: warning: narrowing conversion of ‘G[from].std::vector<_Tp, _Alloc>::size<edge, std::allocator<edge> >()’ from ‘std::vector<edge>::size_type {aka long unsigned int}’ to ‘int’ inside { } [-Wnarrowing]
  edge e1={to,cap,cost,G[to].size()},e2={from,0,-cost,G[from].size()};
                                                                   ^

Judge Result