글 읽기 - 메모리 초과가 어디서 나는지 모르겠습니다 ㅜㅜ

sally0226 2년 전 2

메모리 초과가 계속 나는데.. 뭐가 문제인지 모르겠습니다 ㅜㅜ

/* 벽 부수고 이동하기 */
#include <iostream>
#include <queue>
#include <algorithm>
#include <string>

using namespace std;

int N, M;
bool map[1001][1001];
bool visited[2][1001][1001] = { 0, };
int answer = 987654321;
int dn[4] = { -1,1,0,0 };
int dm[4] = { 0,0,-1,1 }; // 상 하 좌 우

struct Node {
	int n;
	int m;
	int dist;
	bool crashWall;
};
void BFS() {
	queue<Node> q;
	q.push({1,1,1,0}); // idx : 1 ~ N, 1 ~ M 

	while (!q.empty()) {
		Node temp = q.front();
		int n = temp.n;
		int m = temp.m;
		int dist = temp.dist;
		bool crashWall = temp.crashWall;
		q.pop();
		if (n == N && m == M) {
			answer = min(answer, dist);
			//continue;
			break;
		}
		visited[crashWall][n][m] = 1;
		for (int i = 0;i < 4;i++) {
			int new_n = n + dn[i];
			int new_m = m + dm[i];
			
			if (new_n > 0 && new_n <= N && new_m > 0 && new_m <= M) { //map 범위 안인지 확인
				if (map[new_n][new_m]) { //벽
					if (!crashWall && !visited[1][new_n][new_m]) //벽을 부신적이 없고, 해당 위치를 벽을 부신채로 방문한 적이 없으면 
						q.push({ new_n,new_m,dist + 1,1 });
				}
				else { //벽이 아님 
					if (!visited[crashWall][new_n][new_m])
						q.push({ new_n,new_m,dist + 1,crashWall });
				}
			}
		}
	}
}
int main(void) {
	cin >> N >> M;
	string s;
	for (int i = 1;i <= N;i++) {
		cin >> s;
		for (int j = 1;j <= M;j++) {
			map[i][j] = s[j-1] - '0';
		}
	}
	BFS();
	if (answer == 987654321)
		answer = -1;
	cout << answer << endl;
	return 0;
}

proto_type 2년 전 0

방문을 한 다음(q 에 push 하고) 표시를 하지 않아서 계속 다시 방문할 것 같아요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

메모리 초과가 어디서 나는지 모르겠습니다 ㅜㅜ

sally0226 2년 전 2

proto_type 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말