Submission #306256

---

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, int A[55][55]) {
    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]+1 == L[yy][xx] && A[yy][xx]) {
	    ret.push_back( make_pair(yy, xx) );
	}
    }
    return ret;
}

int AZ[55][55], BZ[55][55];

int main() {
    scanf("%d%d", &H, &W);
    int sy, sx;

    REP (i, H) scanf("%s", F[i]);
    REP (i, H) {
	REP (j, W) {
	    if (F[i][j] == 'S') {
		sy = i;
		sx = j;
	    }
	}
    }

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

    path('A', AZ);
    path('B', BZ);

    int ax, ay, bx, by;
    int aex, aey, bex, bey;
    ax = bx = sx;
    ay = by = sy;
    REP (i, H) REP (j, W) {
	if (F[i][j] == 'A') {
	    aex = j;
	    aey = i;
	}
	if (F[i][j] == 'B') {
	    bex = j;
	    bey = i;
	}
    }

    if (L[aey][aex] > 9999 || L[bey][bex] > 9999) NA();

    while (true) {
	if (ax == aex && ay == aey) break;
	if (bx == bex && by == bey) break;
	vector<pair<int, int> >A = search(ay, ax, AZ);
	vector<pair<int, int> >B = search(by, bx, BZ);

	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();
    }

    while (ax != aex || ay != aey)  {
	vector<pair<int, int> >A = search(ay, ax, AZ);
	ay = A[0].first;
	ax = A[0].second;
	F[ay][ax] = 'a';
    }

    while (bx != bex || by != bey)  {
	vector<pair<int, int> >B = search(by, bx, BZ);
	by = B[0].first;
	bx = B[0].second;
	F[by][bx] = 'b';
    }

    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:112:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result