Submission #306146

---

Source Code Expand

#include<queue>
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &a, const T &b) { if (a>b) a=b; }
template<class T> inline void amax(T &a, const T &b) { if (a<b) a=b; }

const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

void NA() {
    puts("NA");
    exit(0);
}

int H, W;
char F[55][55];
int L[55][55], fX[55][55], fY[55][55];

bool in(int y, int x) {
    return 0 <= x && x < W && 0 <= y && y < H;
}

void solve() {
    int sx, sy;
    REP (i, H) REP (j, W) {
	if (F[i][j] == 'S') {
	    sx = j;
	    sy = i;
	}
    }
    memset(L, 0x3f, sizeof L);
    memset(fX, -1, sizeof fX);
    memset(fY, -1, sizeof fY);

    queue<int> qu;
    qu.push(sx); qu.push(sy);
    L[sy][sx] = 0;
    while (qu.size()) {
	int x = qu.front(); qu.pop();
	int y = qu.front(); qu.pop();
	REP (d, 4) {
	    int xx = x + dx[d];
	    int yy = y + dy[d];
	    if (0 <= xx && xx < W && 0 <= yy && yy < H &&
		    F[yy][xx] != '#' &&
		    L[yy][xx] > L[y][x] + 1) {
		L[yy][xx] = L[y][x] + 1;
		qu.push(xx);
		qu.push(yy);
	    }
	}
    }
}

void path(char G, int C[55][55]) {
    int sx, sy;
    REP (i, H) REP (j, W) {
	if (F[i][j] == G) {
	    sx = j;
	    sy = i;
	}
    }
    queue<int> qu;
    qu.push(sx); qu.push(sy);
    C[sy][sx] = 1;
    while (qu.size()) {
	int x = qu.front(); qu.pop();
	int y = qu.front(); qu.pop();
	REP (d, 4) {
	    int xx = x + dx[d];
	    int yy = y + dy[d];
	    if (0 <= xx && xx < W && 0 <= yy && yy < H &&
		    L[yy][xx] == L[y][x] - 1 && C[yy][xx] == 0) {
		C[yy][xx] = 1;
		qu.push(xx);
		qu.push(yy);
	    }
	}
    }
}

vector<pair<int, int> > search(int y, int x) {
    vector<pair<int, int> > ret;
    for (int d=0; d<4; ++d) {
	int xx = x + dx[d];
	int yy = y + dy[d];
	if (in(yy, xx) && L[y][x] > L[yy][xx] && F[yy][xx] == '.') {
	    ret.push_back( make_pair(yy, xx) );
	}
    }
    return ret;
}

// int A[55][55], B[55][55];

int main() {
    scanf("%d%d", &H, &W);
    REP (i, H) scanf("%s", F[i]);

    solve();
//    REP (i, H) {
//	REP (j, W) {
//	    printf("%d ", L[i][j]);
//	}
//	puts("");
//    }

//    path('A', A);
//    path('B', B);
//
    int ax, ay, bx, by;
    REP (i, H) REP (j, W) {
	if (F[i][j] == 'A') {
	    ax = j;
	    ay = i;
	}
	if (F[i][j] == 'B') {
	    bx = j;
	    by = i;
	}
    }

    while (true) {
	if (L[ay][ax] < L[by][bx]) {
	    vector<pair<int, int> >P = search(ay, ax);
	    if (P.size() == 0u) NA();
	    ay = P[0].first;
	    ax = P[0].second;
	    F[ay][ax] = 'a';
	} else if (L[by][bx] < L[ay][ax]) {
	    vector<pair<int, int> >P = search(ay, ax);
	    if (P.size() == 0u) NA();
	    by = P[0].first;
	    bx = P[0].second;
	    F[by][bx] = 'b';
	} else {
	    if (L[ay][ax] == 1) break;
	    vector<pair<int, int> >A = search(ay, ax);
	    vector<pair<int, int> >B = search(by, bx);

	    bool ok = false;
	    REP (i, A.size()) {
		REP (j, B.size()) {
		    if (A[i] != B[j]) {
			ok = true;
			ay = A[i].first;
			ax = A[i].second;
			F[ay][ax] = 'a';
			by = B[j].first;
			bx = B[j].second;
			F[by][bx] = 'b';
			break;
		    }
		}
		if (ok) break;
	    }
	    if (!ok) NA();
	}
    }

    REP (i, H) puts(F[i]);

    return 0;
}

Submission Info

Compile Error

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

Judge Result