글 읽기 - 벽 부수고 이동하기 메모리 초과 질문입니다.

coronal95 5년 전 0

중복된 위치의 좌표를 계속 지나쳐서 메모리 초과가 뜨는 것 같기도 한데.. 어떻게 고쳐야 할 지 감이 잡히지 않습니다. 도와주시면 감사하겠습니다.

#include <cstdio>
#include <queue>
using namespace std;

//x좌표, y좌표, 이동 거리, 벽 부쉈는지의 여부
struct t { int x, y,dist; bool flag; };
int n, m, map[1001][1001], dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 };
bool isRange(int x, int y) { return (x >= 0 && y >= 0 && x < n&&y < m); }

int go() {
	queue<t> que;
	que.push({ 0,0,1,0 });

	while (!que.empty()) {
		int x = que.front().x, y = que.front().y, dist = que.front().dist;
		bool flag = que.front().flag;
		que.pop();
        //도착했다면, dist 출력
		if (x == n - 1 && y == m - 1) return dist;

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i], ny = y + dy[i];
			if (isRange(nx, ny)) {
                //map이 비어있는 공간이라면, dist+1하고 같은 flag 큐에 넣어주기
				if (!map[nx][ny]) que.push({ nx,ny,dist + 1,flag });
                //flag가 false이고(벽 부순 적이 아직 없고) 다음 위치의 map이 벽이라면, 부수고 dist+1
                //flag=ture(벽을 한 번 부쉈음)하고 queue에 넣어주기
				else if (!flag&& map[nx][ny] == 1) que.push({ nx,ny,dist + 1,true });
			}
		}
	}
    //도착하지 못하는 map이라면, -1 출력
	return -1;
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) scanf("%1d", &map[i][j]);

	printf("%d\n", go());
}