Submission #306033

---

Source Code Expand

/*
	Author : ChnLich
*/
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<sstream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<string>
#include<bitset>
#include<functional>
#include<utility>

using namespace std;

typedef long long llint;
typedef pair<int,int> ipair;
typedef unsigned int uint;
#define pb push_back
#define fi first
#define se second
#define mp make_pair

const int MOD=1000000007,dx[]={0,1,0,-1},dy[]={1,0,-1,0};
const double eps=1e-8;

void read(int &k)
{
	k=0; char x=getchar();
	while(x<'0'||x>'9') x=getchar();
	while(x>='0'&&x<='9') { k=k*10-48+x; x=getchar(); }
}

#define MAXN 5010
#define MAXM 500000

char s[55][55];
int n,m,S,p,q;
int vis[5010],dist[5010],last[5010];
int dd[2500*2500+10],ll,rr;

struct graph
{
	int a[MAXN],b[MAXM],c[MAXM],d[MAXM],e[MAXM],l[MAXM],p;
	int fare;
	void clear()
	{
		memset(a,0,sizeof a);
		p=1;
	}
	void addedge(int x,int y,int z=0,int w=0)
	{
		//if(z)printf("%d %d %d %d\n",x,y,z,w);
		c[++p]=a[x]; a[x]=p; b[p]=y; d[p]=z; e[p]=w; l[p]=d[p];
		c[++p]=a[y]; a[y]=p; b[p]=x; d[p]=0; e[p]=-w; l[p]=d[p];
	}
	void bfs(int S)
	{
		for(vis[dd[ll=rr=0]=S]=1;ll<=rr;ll++)
			for(int i=a[dd[ll]];i;i=c[i]) if (!vis[b[i]])
				vis[dd[++rr]=b[i]]=vis[dd[ll]]+1;
	}
	int spfa()
	{
		memset(dist,63,sizeof dist);
		memset(vis,0,sizeof vis);
		dist[0]=0;
		for(vis[dd[ll=rr=0]=0]=1;ll<=rr;ll++)
		{
			vis[dd[ll]]=0;
			for(int i=a[dd[ll]];i;i=c[i]) if (d[i]&&dist[b[i]]>dist[dd[ll]]+e[i])
			{
				dist[b[i]]=dist[dd[ll]]+e[i];
				last[b[i]]=i;
				if (!vis[b[i]])
				{
					vis[b[i]]=1;
					dd[++rr]=b[i];
				}
			}
		}
		int now=n*m*2+1;
		if (dist[now]>=1000000000) return 0;
		fare=0;
		while(now)
		{
			fare+=e[last[now]];
			d[last[now]]-=1;
			d[last[now]^1]+=1;
			now=b[last[now]^1];
		}
		return 1;
	}
	int minfare()
	{
		int ret=0;
		fare=0;
		while(spfa())
			ret+=fare;
		return ret;
	}
	int dfs(int S)
	{
		int col;
		int tx=(S-1)/m+1;
		int ty=(S-1)%m+1;
		for(int i=a[S];i;i=c[i]) if (d[i]<l[i])
		{
			col=dfs(b[i]);
			if (b[i]==S+n*m)
				if (s[tx][ty]=='.') s[tx][ty]=col;
		}
		if (S==::p) col='a';
		if (S==q) col='b';
		
		return col;
	}
} A,B;

int getpos(int x,int y)
{
	return (x-1)*m+y;
}

int main()
{
	//freopen("D.in","r",stdin);
	
	A.clear();
	B.clear();
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) if (s[i][j]!='#')
		{
			if (s[i][j]=='S')
				S=getpos(i,j);
			else if (s[i][j]=='A')
				p=getpos(i,j);
			else if (s[i][j]=='B')
				q=getpos(i,j);
			for(int dir=0;dir<4;dir++)
			{
				int tx,ty;
				tx=i+dx[dir];
				ty=j+dy[dir];
				if (tx>0&&tx<=n&&ty>0&&ty<=m&&s[tx][ty]!='#') 
				{
					A.addedge(getpos(i,j),getpos(tx,ty));
					B.addedge(n*m+getpos(i,j),getpos(tx,ty),1,0);
				}	
			}
			B.addedge(getpos(i,j),n*m+getpos(i,j),1,1);
		}
	A.bfs(S);
	if (vis[p]>=1000000000||vis[q]>=1000000000)
	{
		puts("NA");
		return 0;
	}
	int tot=vis[p]+vis[q]-2;
	B.addedge(0,S+n*m,2,0);
	B.addedge(p+n*m,n*m*2+1,1,0);
	B.addedge(q+n*m,n*m*2+1,1,0);
	int ret=B.minfare();
	if (tot!=ret)
	{
		puts("NA");
		return 0;
	}
	B.dfs(0);
	for(int i=1;i<=n;i++,puts(""))
		for(int j=1;j<=m;j++) printf("%c",s[i][j]);
	
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:143:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:144:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result