글 읽기 - 22% 오류..

gusxoz12 2년 전 0

2차원 배열로 0인 지점에서 bfs 진행해서 계속 0이 위치하는 곳을 바꿔주면서 큐에 넣어주고 탐색을 했는데
어디가 틀렸는지 모르겠습니다...

테스트 케이스는 모두 맞았으나, 22%에서 오답처리가 됩니다....

#include<iostream>
#include<queue>
#include<algorithm>

#define endl '\n' 
#define LOCAL_TEST

using namespace std;

queue<pair<int, int>> q;

int puzzle[3][3];

int target[3][3]={{1,2,3}, 
                    {4,5,6},
                    {7,8,0}};

int dx[4] ={-1,1, 0,0};
int dy[4] ={0,0,-1,1};

int cnt;

bool isInside(int x,int y){
    return 0<=x&& x<3 && 0<=y && y<3;
}
void bfs(int x,int y){
    q.push({x,y});
    
    while(!q.empty()){
        int x = q.front().first;
        int y= q.front().second;
        q.pop();
        if(puzzle[x][y] == target[x][y]) continue;
        for(int i=0;i<4; i++){
            int nx= x +dx[i];
            int ny= y+ dy[i];
            if( isInside(nx,ny) && target[x][y]==puzzle[nx][ny]){
                swap(puzzle[x][y], puzzle[nx][ny]);
                q.push({nx,ny});
                cnt++;
            } 
        }
    }
}

int main()
{   
#ifdef LOCAL_TEST
    freopen("input.txt", "r", stdin);
#endif
    ios_base ::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    
    for(int i=0;i<3;i++)
        for(int j=0;j<3; j++)
            cin>>puzzle[i][j];        

    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++) if(puzzle[i][j]==0)bfs(i,j);

    bool flag =true;
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++) if(target[i][j]!= puzzle[i][j]) flag =false;
    if (flag)cout<<cnt<<endl;
    else cout<<-1<<endl;
    return 0;   
}

bamgoesn 2년 전 0

컴파일을 제대로 했는지 아리까리하긴 한데... 제대로 했다는 전제 하에 반례는 아래와 같습니다.

일단 한번 테스트는 해보시기 바랍니다

4 1 3
2 0 5
7 8 6

정답: 6
출력: -1

과정
4 1 3   4 1 3   0 1 3   1 0 3   1 2 3
2 0 5   0 2 5   4 2 5   4 2 5   4 0 5
7 8 6   7 8 6   7 8 6   7 8 6   7 8 6
(시작)
1 2 3   1 2 3
4 5 0   4 5 6
7 8 6   7 8 0
        (완료)


2 3 5
1 8 0
4 7 6

정답: 9
출력: -1

과정
2 3 5   2 3 0   2 0 3   0 2 3   1 2 3
1 8 0   1 8 5   1 8 5   1 8 5   0 8 5
4 7 6   4 7 6   4 7 6   4 7 6   4 7 6
(시작)
1 2 3   1 2 3   1 2 3   1 2 3   1 2 3
4 8 5   4 8 5   4 0 5   4 5 0   4 5 6
0 7 6   7 0 6   7 8 6   7 8 6   7 8 0
                                (완료)

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

문제

문제

출처

ICPC

22% 오류..

gusxoz12 2년 전 0

bamgoesn 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말