글 읽기 - 방문처리에 대한 질문입니다.

rlarudgh2017 2년 전 0

다른 분들의 질문을 확인하니 큐에서 방문처리를 제대로 못 할 때 메모리 초과가 뜬다고 하시는데

아무리 생각해도 왜 틀린건지를 모르겠습니다. 제가 방문처리를 정말 잘못한게 맞나요????

불이 번진 시간보다 빨리 도착할 때, 벽이 아닐 때, 내가 방문했던 곳이 아닐 때

방문처리를 했습니다.

#include <bits/stdc++.h>
using namespace std;

int visitj[1000][1000];
int visitf[1000][1000];
string maze[1000];
int diry[4] = {0, 0, 1, -1};
int dirx[4] = {1, -1, 0, 0};
int r, c;
bool bts();
int bfs(int posy, int posx);
bool inRange(int posy, int posx);

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    int posy, posx;
    cin >> r >> c;
    for (int i = 0; i < r; ++i) {
        cin >> maze[i];
        for (int j = 0; j < c; ++j) {
            visitj[i][j] = INT_MAX;
            visitf[i][j] = INT_MAX;
            if (maze[i][j] == 'J') {
                posy = i;
                posx = j;
            }
        }
    }
    
    bts();
    int result = bfs(posy, posx);
    if (result < 0)
        cout << "IMPOSSIBLE";
    else
        cout << result;
    
    return 0;
}

bool bts()
{
    queue<pair<int, int>> q;
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            if (maze[i][j] == 'F') {
                q.push({i, j});
                visitf[i][j] = 0;
            }
        }
    }
    if (q.empty())
        return false;

    while (!q.empty()) {
        pair<int, int> cur = q.front(); q.pop();
        for (int i = 0; i < 4; ++i) {
            int nexty = cur.first + diry[i];
            int nextx = cur.second + dirx[i];
            if (!inRange(nexty, nextx) || maze[nexty][nextx] == '#' || visitf[nexty][nextx] <= visitf[cur.first][cur.second])
                continue;
            visitf[nexty][nextx] = visitf[cur.first][cur.second] + 1;
            q.push({nexty, nextx});
        }
    }
    return true;
}

int bfs(int posy, int posx)
{
    queue<pair<int, int>> q;
    q.push({posy, posx});
    visitj[posy][posx] = 0;

    while (!q.empty()) {
        pair<int, int> cur = q.front(); q.pop();
        for (int i = 0; i < 4; ++i) {
            int nexty = cur.first + diry[i];
            int nextx = cur.second + dirx[i];
            if (!inRange(nexty, nextx))
                return visitj[cur.first][cur.second] + 1;
            if (visitj[cur.first][cur.second] + 1 >= visitf[nexty][nextx] || maze[nexty][nextx] != '.')
                continue;
            visitj[nexty][nextx] = visitj[cur.first][cur.second] + 1;
            maze[nexty][nextx] = 'J';
            q.push({nexty, nextx});
        }
    }
    return -1;
}

bool inRange(int posy, int posx)
{
    if (posy < 0 || posy > r - 1)
        return false;
    if (posx < 0 || posx > c - 1)
        return false;
    return true;
}

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

문제

문제

출처

ICPC

방문처리에 대한 질문입니다.

rlarudgh2017 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말