글 읽기 - 메모리 초과에서...

knk3567 3년 전 0

디버깅해보니까 878Kb 정도가 최대인거같은데 왜 초과나는지 모르겠어요...

#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;
int R, C; // R 세로 C 가로
char map[51][51];
int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 };
queue <pair<pair<int, int>, int> > q;
queue <pair<int, int> > w;
void bfs() {
	while (!q.empty()) {
		int x, y, cnt; 
		int wx, wy, ws;
		x = q.front().first.second;
		y = q.front().first.first;
		cnt = q.front().second;
		q.pop();
		ws = w.size();
		for (int i = 0; i < ws; i++) {
			wx = w.front().second;
			wy = w.front().first;
			w.pop();
			for (int i = 0; i < 4; i++) {
				int wdx, wdy;
				wdx = wx + dx[i];
				wdy = wy + dy[i];
				if (wdy >= 0 && wdy < R && wdx >= 0 && wdx < C && map[wdy][wdx] != 'X' && map[wdy][wdx] != 'D' && map[wdy][wdx] != '*') {
					map[wdy][wdx] = '*';
					w.push({ wdy,wdx });
				}
			}
		}
		for (int i = 0; i < 4; i++) {
			int nx, ny;
			nx = x + dx[i];
			ny = y + dy[i];
			if (nx >= 0 && nx < C && ny >= 0 && ny < R && map[ny][nx] != '*' && map[ny][nx] != 'X') {
				if (map[ny][nx] == 'D') {
					cout << cnt + 1 << endl;
					return ;
				}
				else {
					map[ny][nx] = 'S';
					q.push({ { ny,nx }, cnt + 1 });
				}
			}
			
		}
	}
	cout << "KAKTUS" << endl;
}
int main() {
	cin >> R >> C;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> map[i][j];
			if (map[i][j] == 'S') q.push({ { i,j }, 0 });
			if (map[i][j] == '*') w.push({ i,j });
		}
	}
	bfs();
}