Submission #595247


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)
#define eprintf(s...) fprintf(stderr, s)

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

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

int H, W;
char F[99][99];
int D[2][99][99];
bool B[2][99][99];

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

int bfs(char g, int k) {
    queue<int> Y, X;
    REP (i, H) REP (j, W) if (F[i][j] == 'S') {
	Y.push(i);
	X.push(j);
	D[k][i][j] = 0;
    }

    while (Y.size()) {
	int y = Y.front(); Y.pop();
	int x = X.front(); X.pop();
	REP (d, 4) {
	    int yy = y + dy[d];
	    int xx = x + dx[d];
	    if (in(yy, xx) && D[k][yy][xx] > D[k][y][x] + 1 && F[yy][xx] != '#') {
		D[k][yy][xx] = D[k][y][x] + 1;
		Y.push(yy);
		X.push(xx);
	    }
	}
    }

    REP (i, H) REP (j, W) if (F[i][j] == g) {
	if (D[k][i][j] > 10000) return D[k][i][j];
	Y.push(i);
	X.push(j);
	B[k][i][j] = true;
	
	while (Y.size()) {
	    int y = Y.front(); Y.pop();
	    int x = X.front(); X.pop();
	    REP (d, 4) {
		int yy = y + dy[d];
		int xx = x + dx[d];
		if (in(yy, xx) && (F[yy][xx] == 'S' || F[yy][xx] == '.') && D[k][yy][xx] == D[k][y][x] - 1 && !B[k][yy][xx]) {
		    B[k][yy][xx] = true;
		    Y.push(yy);
		    X.push(xx);
		}
	    }
	}
	{
	    REP (i, H) REP (j, W) if (!B[k][i][j]) D[k][i][j] = D[0][98][98];
	}
	return D[k][i][j];
    }
}

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

    memset(D, 0x3f, sizeof D);
    int lenA = bfs('A', 0);
    int lenB = bfs('B', 1);
    
    if (lenA == D[0][98][98] || lenB == D[0][98][98]) {
	puts("NA");
	return 0;
    }

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


    while (F[ay][ax] != 'A' || F[by][bx] != 'B') {
	vector<pair<int, int> > av, bv;
	REP (d, 4) {
	    int yy, xx;
	    yy = ay + dy[d];
	    xx = ax + dx[d];
	    if (in(yy, xx) && D[0][yy][xx] == D[0][ay][ax] + 1) {
		av.push_back(make_pair(yy, xx));
	    }
	    yy = by + dy[d];
	    xx = bx + dx[d];
	    if (in(yy, xx) && D[1][yy][xx] == D[1][by][bx] + 1) {
		bv.push_back(make_pair(yy, xx));
	    }
	}

	pair<int, int> na(-1, -1), nb(-1, -1);
	EACH (ae, av) EACH (be, bv) if (*ae != *be) {
	    na = *ae;
	    nb = *be;
	}
	if (na.first != -1) {
	    ay = na.first; ax = na.second;
	    by = nb.first; bx = nb.second;
	    if (F[ay][ax] == '.') F[ay][ax] = 'a';
	    if (F[by][bx] == '.') F[by][bx] = 'b';
	} else {
	    puts("NA");
	    return 0;
	}
    }

    while (F[ay][ax] != 'A') {
	REP (d, 4) {
	    int yy = ay + dy[d];
	    int xx = ax + dx[d];
	    if (in(yy, xx) && D[0][yy][xx] == D[0][ay][ax] + 1) {
		ay = yy;
		ax = xx;
		if (F[ay][ax] == '.') F[ay][ax] = 'a';
		break;
	    }
	}
    }
    while (F[by][bx] != 'B') {
	REP (d, 4) {
	    int yy = by + dy[d];
	    int xx = bx + dx[d];
	    if (in(yy, xx) && D[1][yy][xx] == D[1][by][bx] + 1) {
		by = yy;
		bx = xx;
		if (F[by][bx] == '.') F[by][bx] = 'b';
		break;
	    }
	}
    }

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

    return 0;
}

Submission Info

Submission Time
Task D - Maze
User natsugiri
Language C++ (G++ 4.6.4)
Score 0
Code Size 3595 Byte
Status WA
Exec Time 31 ms
Memory 1176 KB

Compile Error

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

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
AC × 20
WA × 21
Set Name Test Cases
all manual_j1.txt, manual_j10.txt, manual_j11.txt, manual_j12.txt, manual_j13.txt, manual_j14.txt, manual_j15.txt, manual_j2.txt, manual_j3.txt, manual_j4.txt, manual_j5.txt, manual_j6.txt, manual_j7.txt, manual_j8.txt, manual_j9.txt, manual_k1.txt, manual_k2.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_max_01.txt, random_max_02.txt, random_max_03.txt, random_max_04.txt, random_max_05.txt, random_max_06.txt, random_max_07.txt, random_max_08.txt, random_max_09.txt, random_max_10.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, white_01.txt, white_02.txt, white_03.txt, white_04.txt
Case Name Status Exec Time Memory
manual_j1.txt AC 29 ms 1108 KB
manual_j10.txt AC 26 ms 1068 KB
manual_j11.txt WA 28 ms 1172 KB
manual_j12.txt AC 27 ms 1176 KB
manual_j13.txt AC 27 ms 1108 KB
manual_j14.txt AC 27 ms 1164 KB
manual_j15.txt WA 26 ms 1132 KB
manual_j2.txt WA 27 ms 1076 KB
manual_j3.txt AC 27 ms 1176 KB
manual_j4.txt WA 29 ms 1072 KB
manual_j5.txt WA 27 ms 1172 KB
manual_j6.txt AC 26 ms 1072 KB
manual_j7.txt WA 26 ms 1076 KB
manual_j8.txt AC 31 ms 1076 KB
manual_j9.txt WA 27 ms 1072 KB
manual_k1.txt WA 27 ms 1168 KB
manual_k2.txt AC 27 ms 1076 KB
random_01.txt AC 27 ms 1172 KB
random_02.txt WA 26 ms 1064 KB
random_03.txt WA 26 ms 1072 KB
random_04.txt WA 28 ms 1168 KB
random_05.txt WA 27 ms 1076 KB
random_06.txt AC 26 ms 1076 KB
random_max_01.txt WA 27 ms 1172 KB
random_max_02.txt WA 27 ms 1076 KB
random_max_03.txt AC 28 ms 1120 KB
random_max_04.txt AC 28 ms 1168 KB
random_max_05.txt WA 25 ms 1168 KB
random_max_06.txt WA 27 ms 1164 KB
random_max_07.txt WA 27 ms 1176 KB
random_max_08.txt WA 27 ms 1168 KB
random_max_09.txt AC 26 ms 1136 KB
random_max_10.txt AC 27 ms 1072 KB
sample_01.txt AC 26 ms 1072 KB
sample_02.txt AC 26 ms 1172 KB
sample_03.txt AC 27 ms 1172 KB
sample_04.txt AC 26 ms 1168 KB
white_01.txt WA 26 ms 1172 KB
white_02.txt WA 27 ms 1176 KB
white_03.txt WA 27 ms 1072 KB
white_04.txt AC 27 ms 1072 KB