글 읽기 - 50%에서 계속 틀렸다고 나오네요..

rlatmdals9 6년 전 0

예제는 모두 정답으로 나오고 알고리즘에 이상이 없다고 생각하는데 자꾸 틀리다고 나오네요.

방문했던 정점은 다시 방문 못하게 했는데 이게 문제가 될까요??

방문했던 정점도 방문 가능하게 하면 당연히 시간초과가 날 것 같아서요 ㅠㅠ

#include <iostream>
#include <queue>

using namespace std;

bool map[301][301];
const int dir[8][2] = {
    { -2, -1 },
    { -1, -2 },
    { 1, -2 },
    { 2, -1 },
    { 2, 1 },
    { 1, 2 },
    { -1, 2 },
    { -2, 1 }
};

int main(void)
{
    int num_of_case;
    
    cin >> num_of_case;
    
    for(int cnt = 0; cnt < num_of_case; ++cnt)
    {
        queue<pair<int, int>> q;
        int size = 0;
        int target_x = 0, target_y = 0;
        int start_x = 0, start_y = 0;
        int quota = 0, depth = 0;
        
        cin >> size;
        
        for(int i = 0; i < size; ++i)
        {
            for(int j = 0; j < size; ++j)
            {
                map[i][j] = false;
            }
        }
        
        cin >> start_x >> start_y;
        cin >> target_x >> target_y;
        q.push(make_pair(start_x, start_y));
        
        quota = 1;
        depth = 0;
        
        while(true)
        {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            
            if(x == target_x && y == target_y)
            {
                break;
            }
            
            if(quota == 0)
            {
                quota = (int)q.size();
                depth++;
            }
            
            for(int i = 0; i < 8; ++i)
            {
                int dx = x + dir[i][0];
                int dy = y + dir[i][1];
                
                if(dx >= 0 && dx < size && dy >= 0 && dy < size && map[dy][dx] == false)
                {
                    q.push(make_pair(dx, dy));
                    map[dy][dx] = true;
                }
            }
            quota--;
        }
        cout << depth << endl;
    }
    return 0;
}

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

문제

문제

출처

ICPC

50%에서 계속 틀렸다고 나오네요..

rlatmdals9 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말