글 읽기 - 93%에서 틀렸다고 나오는데 어디가 틀린지 모르겠습니다..(C++)

leeh4743 2년 전 0

시작지점부터 BFS를 돌려서 각 지점마다의 거리를 구해주고 마지막에 갈수있는 땅이지만 갈수없는 땅으로 막혀있어 가지못한곳을 탐색해서 -1로 바꿔주는 방식으로 풀이하였습니다.

그리고 처음 위치는 visited 배열에서 그대로 2로 나오길래 나중에 BFS를 모두돌고 0으로 바꿔주었습니다.

제가 해본 입력은 모두 맞게 뜨는데 틀렸다고 나오네요..

틀린부분과 반례를 알 수 있을까요?

#include <iostream>
#include <queue>

using namespace std;

int n,m,u,k;
int map[1000][1000];
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
queue<pair<int, int>> q;
int visited[1000][1000]={0,};

void print()
{
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            cout<<visited[i][j]<<' ';
        }
        cout<<endl;
    }
}

void BFS(int a,int b)
{
    q.push({a, b});
    
    while(q.size())
    {
        int a = q.front().first;
        int b = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++) // 상하좌우 갈수있는 땅 탐색
        {
            int nx = a + dx[i];
            int ny = b + dy[i];
            
            if(nx < 0 || nx >= n || ny < 0 || ny >= n || map[nx][ny] == 0 || visited[nx][ny])
                continue; // 갈수 없거나 이미 방문한곳이면 컨티뉴
            
            q.push({nx, ny});
            visited[nx][ny] = visited[a][b] + 1;
        
        }
        
    }
    
    visited[u][k]=0; // 2로 지정한 처음위치를 0으로 처리해줌.
}


void solve()
{
    cin>>n>>m;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            cin>>map[i][j];
            if(map[i][j]==2) // 목표지점 좌표 저장
            {
                u=i;
                k=j;
            }
        }
    }
    BFS(u,k);
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(visited[i][j]==0&&map[i][j]==1) // 갈수있는 땅이지만 가지못해서 방문배열이 0으로 처리된구역을 -1로 해줌
                visited[i][j]=-1;
        }
    }
    print();
}

int main()
{
    solve();
}

kln99988 1년 전 0

40번째 줄 if(nx < 0 || nx >= n || ny < 0 || ny >= n || map[nx][ny] == 0 || visited[nx][ny])에서 ny>=m으로 고치니까 되네요

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

문제

문제

출처

ICPC

93%에서 틀렸다고 나오는데 어디가 틀린지 모르겠습니다..(C++)

leeh4743 2년 전 0

kln99988 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말