글 읽기 - [C++] 무한 루프에 들어가는 이유를 모르겠습니다.

lyny123 1년 전 0

테스트 케이스를 1개로 하고 하면 되는데 개수를 늘리면 무한 루프에 들어갑니다.

또 채점은 메모리 초과라고 하네요.. 원인 아시는 분들 알려주시면 감사하겠습니다..!

#include <iostream>
#include <queue>

using namespace std;


int mx[4] = {-2,-1,1,2};
int my[4][2] = {{-1,1},{-2,2},{-1,1},{-2,2}};
int bfs(int I, int x, int y, int dx, int dy) {
    int** hits = new int*[I];
    bool** visited = new bool*[I];
    for(int i = 0; i< I; i++){
        hits[i] = new int[I];
        visited[i] = new bool[I];
    }
    for (int j = 0; j < I; j++) {
        for (int k = 0; k < I; k++) {
            hits[j][k] = 0;
            visited[j][k] = false;
        }
    }
    queue<pair<int,int>> q;
    q.push({x,y});
    while(!q.empty()){
        int xx = q.front().first;
        int yy = q.front().second;
        visited[xx][yy] = true;
        q.pop();
        for(int i = 0; i<4; i++){
            for(int j = 0; j<2; j++){
                int nx = xx + mx[i];
                int ny = yy + my[i][j];
                if(nx >= 0 && nx<= I-1 && ny >= 0 && ny <= I-1 && !visited[nx][ny]){
                    q.push({nx, ny});
                    if(hits[nx][ny] > 0) hits[nx][ny] = min(hits[nx][ny],hits[xx][yy] + 1);
                    else hits[nx][ny] = hits[xx][yy] + 1;
                }
            }
        }
    }
    return hits[dx][dy];
}

int main() {
    int T;
    cin >> T;
    for (int i = 0; i < T; i++) {
        int I;
        cin >> I;
        int x, y, dx, dy;
        cin >> x >> y;
        cin >> dx >> dy;
        cout << bfs(I, x, y, dx, dy) << "\n";
    }
    return 0;
}

peydihalta 1년 전 0

큐에서 꺼낼 때 방문체크를 하고 계신데, 넣을 때 방문체크를 하지 않으면 중복으로 들어갑니다.

lyny123 1년 전 0

감사합니다..! 무한 루프에서 나왔어요..!

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

문제

문제

출처

ICPC

[C++] 무한 루프에 들어가는 이유를 모르겠습니다.

lyny123 1년 전 0

peydihalta 1년 전 0

lyny123 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말