3-D 불! 메모리 초과 질문 있습니다.

작성한 질문수 3

0

안녕하세요 ㅎㅎ

이렇게 고쳐보시겠어요?

            if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
            if (person_check[ny][nx] || a[ny][nx] == '#') continue;
            if (fire_check[ny][nx] <= person_check[y][x] + 1) continue;
            person_check[ny][nx] = person_check[y][x] + 1;

전체코드 :

#include <bits/stdc++.h>
using namespace std;
const int max_n = 1004;
const int INF = 987654321;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
char a[max_n][max_n];
int fire_check[max_n][max_n], person_check[max_n][max_n];
int n, m, ans, sy, sx, y, x;
void bfs_fire() {
    queue<pair<int, int>> q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 'F') {
                fire_check[i][j] = 1;
                q.push({i, j});
            }
        }
    }
    while (!q.empty()) {
        tie(y, x) = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int ny = dy[i] + y;
            int nx = dx[i] + x;
            if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
            if (fire_check[ny][nx] != INF || a[ny][nx] == '#') continue;
            fire_check[ny][nx] = fire_check[y][x] + 1;
            q.push({ny, nx});
        }
    }
}
int bfs_person() {
    queue<pair<int, int>> q;
    person_check[sy][sx] = 1;
    q.push({sy, sx});

    while (!q.empty()) {
        tie(y, x) = q.front();
        q.pop();
        if (x == m - 1 || y == n - 1 || x == 0 || y == 0) {
            return person_check[y][x];
        }
        for (int i = 0; i < 4; i++) {
            int ny = dy[i] + y;
            int nx = dx[i] + x;
            if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
            if (person_check[ny][nx] || a[ny][nx] == '#') continue;
            if (fire_check[ny][nx] <= person_check[y][x] + 1) continue;
            person_check[ny][nx] = person_check[y][x] + 1;
            q.push({ny, nx});
        }
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    fill(&fire_check[0][0], &fire_check[0][0] + 1004 * 1004, INF);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            if (a[i][j] == 'J') {
                sy = i;
                sx = j;
            }
        }
    }
    bfs_fire();
    ans = bfs_person();
    if (ans != 0) cout << ans << "\n";
    else cout << "IMPOSSIBLE" << "\n";
    return 0;
}

사실 이게 좀 이상해서 수정해서 제출했더니 맞았다고 뜨는데요.

#은 아스키코드로 23을 뜻합니다. 23과 비교하니 해당 부분의 로직이 잘못된 셈인 것이죠..

이부분에서 문제가 떠서 UB >> 메모리초과

이렇게 이어지지 않았나 생각이 듭니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.