Submission #306522

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
const int N = 55;
int way[4][2] = {0 , 1 , 0 , -1 , 1 , 0 , -1 , 0};
char str[N][N];
int vis[N][N] , dist[N][N] , n , m;
pair <int , int> s , a , b;
int mindist (pair <int , int> s , pair <int , int> t) {
	queue <pair <int , int> > que;
	que.push (s);
	memset (vis , 0 , sizeof (vis));
	vis[s.first][s.second] = 1;
	dist[s.first][s.second] = 0;
	while (!que.empty ()) {
		pair <int , int> v , u = que.front ();
		que.pop ();
		for (int i = 0 ; i < 4 ; i ++) {
			v = u;
			v.first += way[i][0];
			v.second += way[i][1];
			if (v.first >= 0 && v.second >= 0 && v.first < n & v.second < m) {
				if (vis[v.first][v.second] == 0 && str[v.first][v.second] != '#') {
					vis[v.first][v.second] = 1;
					que.push (v);
					dist[v.first][v.second] = dist[u.first][u.second] + 1;
				}
			}
		}
	}
	if (vis[t.first][t.second] == 0) return -1;
	return dist[t.first][t.second];
}
struct Edge {
	int u , v , w , c , next;
}e[N * N * N * 10];
const int INF = 1000000007;
vector <int> adj[N * N * 2];
int source , sink;
int dis[N * N * 2];
int tot , head[N * N * 2] , pre[N * N * 2] , inq[N * N * 2];
// w为流量，c为费用
void add_edge(int u,int v,int w,int c){
    e[tot].u = u , e[tot].v = v , e[tot].w = w ,e[tot].c = c;
    e[tot].next = head[u] , head[u] = tot ++;
}
void _add(int u,int v,int w,int c){
    add_edge(u,v,w,c);
    add_edge(v,u,0,-c);
}
bool spfa() {
    queue<int> q;
    memset(pre,-1,sizeof(pre));
    memset(inq,false,sizeof(inq));
    memset(dis,0x3f,sizeof(dis));
    dis[source] = 0 , inq[source] = true;
    q.push(source);
    while(! q.empty()){
        int u = q.front();q.pop();
        for(int i = head[u];i != -1;i = e[i].next){
            int v = e[i].v;
            if(e[i].w && dis[v] > dis[u] + e[i].c){
                pre[v] = i;
                dis[v] = dis[u] + e[i].c;
                if(! inq[v]){
                    inq[v] = true;
                    q.push(v);
                }
            }
        }
        inq[u] = false;
    }
    return dis[sink] != 0x3f3f3f3f;
}
pair <int , int> mincost_maxflow() {
    int mincost,maxflow;
    mincost = maxflow = 0;
    while(spfa()){
        int flow = INF;
        for(int i = pre[sink];i != -1;i = pre[e[i].u])
            if(e[i].w < flow) flow = e[i].w;
        maxflow += flow;
        mincost += dis[sink] * flow;
        for(int i = pre[sink];i != -1;i = pre[e[i].u]){
            e[i].w -= flow;
            e[i ^ 1].w += flow;
        }
    }
    return make_pair (maxflow , mincost);
}
void dfs (int u , char ch) {
	int x = u / m , y = u % m;
	if (str[x][y] == '.') {
		str[x][y] = ch;
	}
	for (int i = 0 ; i < adj[u].size () ; i ++) {
		int v = adj[u][i];
		dfs (v , ch);
	}
}
int main () {
	// freopen ("input.txt" , "r" , stdin);
	tot = 0;
	memset (head , -1 , sizeof (head));
	scanf ("%d %d" , &n , &m);
	for (int i = 0 ; i < n ; i ++) {
		scanf ("%s" , str[i]);
		for (int j = 0 ; j < m ; j ++) {
			if (str[i][j] == 'S') s = make_pair (i , j);
			if (str[i][j] == 'A') a = make_pair (i , j);
			if (str[i][j] == 'B') b = make_pair (i , j);
		}
	}
	int da = mindist (s , a);
	int db = mindist (s , b);

	if (da == -1 || db == -1) {
		puts ("NA");
		return 0;
	}
	source = 0;
	sink = n * m * 2 + 1; 
	for (int i = 0 ; i < n ; i ++) {
		for (int j = 0 ; j < m ; j ++) {
			if (str[i][j] == '#') continue;
			int u = i * m + j + 1;
			_add (u , u + n * m , 1 , 0);
		}
	}
	int start = tot;
	for (int i = 0 ; i < n ; i ++) {
		for (int j = 0 ; j < m ; j ++) {
			int u = i * m + j + 1;
			for (int dir = 0 ; dir < 4 ; dir ++) {
				int x = i + way[dir][0];
				int y = j + way[dir][1];
				if (x >= 0 && y >= 0 && x < n && y < m) {
					int v = x * m + y + 1;
					_add (u + n * m , v , 1 , 1);
				}
			}
		}
	}
	for (int i = 0 ; i < 4 ; i ++) {
		int x = s.first + way[i][0];
		int y = s.second + way[i][1];
		if (x >= 0 && y >= 0 && x < n && y < m) {
			_add (0 , x * m + y + 1 , 1 , 1);
		}
	}
	int end = tot;
	for (int i = 0 ; i < 1 ; i ++) {
		int x = a.first;
		int y = a.second;
		if (x >= 0 && y >= 0 && x < n && y < m) {
			_add (x * m + y + 1 + n * m , sink , 1 , 0);
		}
	}
	for (int i = 0 ; i < 1 ; i ++) {
		int x = b.first ;
		int y = b.second;
		if (x >= 0 && y >= 0 && x < n && y < m) {
			_add (x * m + y + 1 + n * m , sink , 1 , 0);
		}
	}
	// cout << da << " " << db << endl;
	pair <int , int> ans = mincost_maxflow ();
	if (ans.first != 2 || ans.second != da + db) {
		puts ("NA");
		return 0;
	}
	for (int i = start ; i < end ; i += 2) {
		if (e[i].w != 1) {
			int u = e[i].u , v = e[i].v;
			if (u == 0) {
				adj[v - 1].push_back (s.first * m + s.second);
			}
			else {
				adj[v - 1].push_back (u - n * m - 1);
			}
		}
	}
	dfs (a.first * m + a.second , 'a');
	dfs (b.first * m + b.second , 'b');
	for (int i = 0 ; i < n ; i ++)
		puts (str[i]);
	return 0;
}

Submission Info

Compile Error

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

Judge Result