Submission #306413

---

Source Code Expand

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<time.h>
#include<vector>
#include<string.h>
#include<algorithm>
#include<ctype.h>
#include<queue>
#include<stack>
#include<string>
using namespace std;
typedef long long lld;//%lld

#define LL(x) ((x)<<1)
#define RR(x) ((x)<<1|1)

const int MAX = 5100*2;
const int INF = 1000000000;
const int MOD = 1000000;
struct EDGE
{
	int cap, cost, v, next;
}edge[MOD];
int head[MAX], E, q[MOD];
bool used[MAX];
int pre[MAX], cur[MAX], dis[MAX];
void add_edge(int s, int t, int cap, int cost)
{
	edge[E].cap = cap;
	edge[E].cost = cost;
	edge[E].next = head[s];
	edge[E].v = t;
	head[s] = E++;
}
int min(int a, int b){ return (a == -1 || b<a) ? b : a; }
int SPFA(int s, int t, int n)
{
	int f = -1, r = 0;
	int i, v;
	q[r] = s;
	for (i = 0; i<n; i++)
	if (i == s)
		dis[i] = 0;
	else dis[i] = INF;
	pre[s] = s;
	cur[s] = -1;
	memset(used, false, sizeof(bool)*n);
	used[s] = true;
	while (f != r)
	{
		f++;
		if (f >= MOD)f -= MOD;
		s = q[f];
		used[s] = false;
		for (i = head[s]; i != -1; i = edge[i].next)
		{
			v = edge[i].v;
			if (edge[i].cap>0 && dis[s] + edge[i].cost<dis[v])
			{
				dis[v] = dis[s] + edge[i].cost;
				pre[v] = s;
				cur[v] = i;
				if (!used[v])
				{
					used[v] = true;
					r++;
					if (r >= MOD)r -= MOD;
					q[r] = v;
				}
			}
		}
	}
	return dis[t];
}
int MinCost(int s, int t, int n)
{
	int ans = 0;
	int u, v, cap;
	int cost;
	while (1)
	{
		cost = SPFA(s, t, n);
		if (cost == INF)break;
		u = v = t;
		cap = -1;
		for (u = pre[u]; v != s; v = u, u = pre[u])
		{
			cap = min(cap, edge[cur[v]].cap);
		}
		ans += cost*cap;
		u = v = t;
		for (u = pre[u]; v != s; v = u, u = pre[u])
		{
			edge[cur[v]].cap -= cap;
			edge[cur[v] ^ 1].cap += cap;
		}
	}
	return ans;
}
struct Point
{
	int x, y;
	Point(){}
	Point(int x,int y):x(x),y(y){}
}A,B,S;
queue<Point>qq;
const int MM=55;
char sm[55][55];
int dd[55][55], vv[55][55];
const int dir[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
bool inside(int x, int n){ return x >= 0 && x < n; }
bool chos[55][55];
int BFS(Point S,Point T,int n,int m)
{
	memset(vv, 0, sizeof(vv));
	memset(dd, -1, sizeof(dd));
	dd[S.x][S.y] = 0;
	vv[S.x][S.y] = true;
	int i, j, size;
	while (!qq.empty())qq.pop();
	qq.push(S);
	while(!qq.empty())
	{
		size = qq.size();
		while(size--)
		{
			int x = qq.front().x;
			int y = qq.front().y;
			qq.pop();
			for (i=0;i<4;i++)
			{
				int tx = x + dir[i][0];
				int ty = y + dir[i][1];
				if(inside(tx,n)&&inside(ty,m))
				{
					if (sm[tx][ty] == '#')continue;
					//if (tx == T.x&&ty == T.y)return dd[x][y] + 1;
					if(!vv[tx][ty])
					{
						vv[tx][ty] = true;
						qq.push(Point(tx, ty));
						dd[tx][ty] = dd[x][y] + 1;
					}
				}
			}
		}
	}

	return dd[T.x][T.y];
}
void round(int x,int y,int n,int m)
{
	int i, tx, ty;
	for (i=0;i<4;i++)
	{
		tx = x + dir[i][0];
		ty = y + dir[i][1];
		if (!inside(tx, n) || !inside(ty, m))continue;
		if (sm[tx][ty] == '#')continue;
		int N = n*m;
		add_edge(x*m + y + 1 + N, tx*m + ty + 1, 1, 1);
		add_edge(tx*m + ty + 1,x * m + y + 1 + N, 0, -1);
	}
}
void Search(int x,int y,int n,int m,char c)
{
	int N = n*m;
	int p = x*m + y + 1 + N;
	int ps = S.x*m + S.y + 1;
	int pa = A.x*m + A.y + 1;
	int pb = B.x*m + B.y + 1;
	while(p!=ps)
	{
		if(p<=N&&p!=ps&&p!=pa&&p!=pb)
		{
			sm[(p - 1) / m][(p - 1) % m] = c;
		}
		int i,j;
	//printf("p=%d ", p);		getchar();
		for (i=head[p];i!=-1;i=edge[i].next)
		{

			if(edge[i].cap>0)
			{
				j = edge[i].v;
				//printf("j=%d\n", j);
				if(p>N&&j==p-N)
				{
					p = edge[i].v;
					//puts("aa");
					break;
				}
				else if (p <= N)
				{
					if (p == j)continue;
					//puts("vv");
					p = j;
					break;
				}
			}
		}
		//printf("p=%d ", p);		getchar();
	}
}
int main()
{
	int n,m;
	int i, j;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(chos, 0, sizeof(chos));
		for (i=0;i<n;i++)
		{
			scanf("%s", sm[i]);
			for (j=0;j<m;j++)
			{
				if(sm[i][j]=='A')
				{
					A.x = i;
					A.y = j;
				}
				else if(sm[i][j]=='B')
				{
					B.x = i;
					B.y = j;
				} 
				else if (sm[i][j]=='S')
				{
					S.x = i;
					S.y = j;
				}
			}
		}
		//puts("aa");
		int da = BFS(S,A,n,m);
		int db = BFS(S, B, n, m);
		//printf("da=%d db=%d\n", da, db);
		if(da==-1||db==-1)
		{
			//puts("tt===");
			puts("NA");
			continue;
		}
		int s = 0;
		int t = n*m * 2 + 1;
		E = 0;
		memset(head, -1, sizeof(int)*(t + 1));
		add_edge(s, S.x*m + S.y+1, 2, 0);
		add_edge(1+S.x*m + S.y, s, 0, 0);
		int N = n*m;
		for (i=0;i<n;i++)
		{
			for (j=0;j<m;j++)
			{
				if(sm[i][j]!='#')
				{
					if(i==S.x&&j==S.y)
					{
						add_edge(i*m + j + 1, i*m + j + N + 1, 2, 0);
						add_edge(i*m + j + N + 1, i*m + j + 1, 0, 0);
					}
					else
					{
						add_edge(i*m + j+1, i*m + j+N+1, 1, 0);
						add_edge(i*m + j+N+1, i*m + j+1, 0, 0);
					}
					round(i,j,n,m);
				}
			}
		}
		add_edge(A.x*m+A.y+1+N,t,1,0);
		add_edge(t, A.x*m + A.y + 1 + N, 0, 0);
		add_edge(B.x*m + B.y + 1 + N, t, 1, 0);
		add_edge(t, B.x*m + B.y + 1 + N, 0, 0);
		int ans = MinCost(s, t, t + 1);
		//printf("ans=%d\n", ans);
		if(ans!=da+db)
		{
			//puts("tx");
			puts("NA");
			continue;
		}
		bool flag = true;
		for (i=head[s];i!=-1;i=edge[i].next)
		{
			if(edge[i].cap!=0)
			{
				flag = false;
			}
		}
		if(!flag)
		{
			puts("NA");
			continue;
		}
		//puts("bb");
		Search(A.x, A.y, n, m,'a');
		//puts("xx");
		/*j = 2500;
		for (i=head[j];i!=-1;i=edge[i].next)
		{
			printf("v=%d cap=%d cost=%d\n", edge[i].v, edge[i].cap, edge[i].cost);
		}*/
		Search(B.x,B.y,n,m,'b');
		getchar();
		for (i = 0; i < n; i++)puts(sm[i]);
	}
	return 0;
}

/*
50 50
S.................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
................................................AB
*/

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:214:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%s", sm[i]);
                      ^

Judge Result