글 읽기 - 메모리초과

serity 4년 전 0

69%에서 메모리 초과 나옵니다
아무리 생각해도 메모리 초과 생길 곳은 큐 밖에 없는데 문제를 못찾겠어요ㅠㅠ
#include<iostream>
#include<queue>
using namespace std;
typedef pair<bool, int> pbi;

int n, visited[2][2500], ans = 0;
int dx[] = { -1,-1,-1,0,0,1,1,1 }, dy[] = { -1,0,1,-1,1,-1,0,1 };
char board[51][51];
int move(int start, int st) {
	queue<pbi> q;
	q.push(pbi(st, start));
	visited[st][start] = 1;
	int dist = 0;
	while (!q.empty()) {
		int size = q.size();
		for (int i = 0; i < size; i++) {
			int curr = q.front().second, st = q.front().first;
			q.pop();
			if (st == 0) {
				int X = curr / n, Y = curr % n;
				if (board[X][Y] == 'E') {
					if (board[X - 1][Y] == 'E' && board[X + 1][Y] == 'E') {
						ans = 1;
						return dist;
					}
				}
				int pos = X - 2;
				if (pos >= 0 && board[pos][Y] != '1') {
					if (!visited[st][curr - n]) {
						q.push(pbi(st, curr - n));
						visited[st][curr - n] = 1;
					}
				}
				pos = X + 2;
				if (pos < n && board[pos][Y] != '1') {
					if (!visited[st][curr + n]) {
						q.push(pbi(st, curr + n));
						visited[st][curr + n] = 1;
					}
				}
				int y = Y - 1, x[3] = { X - 1,X,X + 1 };
				if (y >= 0) {
					int flag = 1;
					for (int i = 0; i < 3; i++) {
						if (board[x[i]][y] == '1') {
							flag = 0;
							break;
						}

					}
					if (flag) {
						if (!visited[st][curr - 1]) {
							q.push(pbi(st, curr - 1));
							visited[st][curr - 1] = 1;
						}
					}
				}
				y = Y + 1;
				if (y < n) {
					int flag = 1;
					for (int i = 0; i < 3; i++) {
						if (board[x[i]][y] == '1') {
							flag = 0;
							break;
						}
					}
					if (flag) {
						if (!visited[st][curr + 1]) {
							q.push(pbi(st, curr + 1));
							visited[st][curr + 1] = 1;
						}
					}
				}
				int flag = 1;
				for (int i = 0; i < 8; i++) {
					int X2 = X + dx[i], Y2 = Y + dy[i];
					if (X2 < 0 || Y2 < 0 || X2 >= n || Y2 >= n) {
						flag = 0;
						break;
					}
					if (board[X2][Y2] == '1') {
						flag = 0;
						break;
					}
				}
				if (flag) {
					if (!visited[1][curr]) {
						q.push(pbi(1, curr));
						visited[1][curr] = 1;
					}
				}
			}
			else {
				int X = curr / n, Y = curr % n;
				if (board[X][Y] == 'E') {
					if (board[X][Y - 1] == 'E' && board[X][Y + 1] == 'E') {
						ans = 1;
						return dist;
					}
				}
				int x = X - 1, y[3] = { Y - 1,Y, Y + 1 };
				if (x >= 0) {
					int flag = 1;
					for (int i = 0; i < 3; i++) {
						if (board[x][y[i]] == '1') {
							flag = 0;
							break;
						}

					}
					if (flag) {
						if (!visited[st][curr - n]) {
							q.push(pbi(st, curr - n));
							visited[st][curr - n] = 1;
						}
					}
				}
				x = X + 1;
				if (x < n) {
					int flag = 1;
					for (int i = 0; i < 3; i++) {
						if (board[x][y[i]] == '1') {
							flag = 0;
							break;
						}
					}
					if (flag) {
						if (!visited[st][curr + n]) {
							q.push(pbi(st, curr + n));
							visited[st][curr + n] = 1;
						}
					}
				}

				int pos = Y - 2;
				if (pos >= 0 && board[X][pos] != '1') {
					if (!visited[st][curr - 1]) {
						q.push(pbi(st, curr - 1));
						visited[st][curr - 1] = 1;
					}
				}
				pos = Y + 2;
				if (pos < n && board[X][pos] != '1') {
					if (!visited[st][curr + 1]) {
						q.push(pbi(st, curr + 1));
						visited[st][curr + 1] = 1;
					}
				}

				int flag = 1;
				for (int i = 0; i < 8; i++) {
					if (board[X + dx[i]][Y + dy[i]] == '1') {
						flag = 0;
						break;
					}
				}
				if (flag) {
					if (!visited[0][curr]) {
						q.push(pbi(0, curr));
						visited[0][curr] = 1;
					}
				}
			}
		}
		dist++;
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%s", board[i]);
	}
	int start = -1, state;
	for (int i = 0; i < n; i++) {
		int flag = 0;
		for (int j = 0; j < n; j++) {
			if (board[i][j] == 'B') {
				if (j == n - 1) {
					start = (i + 1)*n + j;
					state = 0;
				}
				else {
					if (board[i][j + 1] == 'B') {
						start = i * n + j + 1;
						state = 1;
					}
					else {
						start = (i + 1)*n + j;
						state = 0;
					}
				}
				flag = 1;
				break;
			}
		}
		if (flag)break;
	}
	if (start == -1) {
		printf("0\n");
		return 0;
	}
	int ret = move(start, state);
	if (ans == 0)printf("0\n");
	else printf("%d\n", ret);



	return 0;
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

메모리초과

serity 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
