글 읽기 - 쨰로탈출2 다른 테스트케이스 관련 질문있습니다.

asd0113 7년 전 0

해당 코드의 알고리즘은 BFS방식으로 시도하였습니다.

알고리즘은 다음과 같은 방식으로 진행합니다.

1. queue의 front부분에서 위치 정보 하나를 얻어서 위, 아래, 오른쪽, 왼쪽으로 공을 굴립니다.

2. 공을 굴리는 방식은 각 방향으로 공의 위치를 이동시킨 후, 공이 겹쳤을 경우 원래의 공 위치를 고려하여 다시 공을 이동시켜줍니다.

(공이 겹친 부분은 코드에서 // overlaped 아래 부분을 참고하시면 됩니다.)

3. 빨간 공이 구멍이 들어갔을 경우 성공 플래그를 true 해주고, 파란 공이 구멍에 들어갔을 경우 실패 플래그를 true로 해줍니다.

4. 실패 플래그가 false일 경우에 한해서 성공 플래그가 true일 경우 원래 위치까지 도달한 경우의 step의 +1의 값을 return하고, 그렇지 않을 경우 다음 경우를 위해 위치 정보를 queue에 넣습니다.

1~4를 반복합니다.

나와있는 테스트 케이스는 모두 맞았으며, 11번 째 step까지 수행하는 테스트 케이스까지 만들어 보았지만 실패했습니다.

10 10
##########
#BR......#
#......#.#
#........#
######.###
#....#...#
#....##..#
#........#
#......O##
##########

예를 들면, 해당 케이스로 시도해 보았으며, 11번 째 시도를 할 경우 실패합니다.

그래서 다른 테스트 케이스가 도저히 떠오르지 않아 질문 게시판에 도움을 요청하고자 합니다.

감사합니다.

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

#define LIMIT_STEP 10
#define MAP_MAX 10
#define UP 0
#define RIGHT 1
#define DOWN 2
#define LEFT 3
#define MOVING_MAX 4

using namespace std;

int N, M;
int Map[MAP_MAX][MAP_MAX];
bool Visited[MAP_MAX][MAP_MAX][MAP_MAX][MAP_MAX];

const int DX[4] = {-1, 0, 1, 0};
const int DY[4] = {0, 1, 0, -1};

struct Ball
{
    int rx, ry, bx, by;
    int step;

    Ball(int _rx, int _ry, int _bx, int _by, int _step)
        : rx(_rx), ry(_ry), bx(_bx), by(_by), step(_step) { }
};

int moving_ball(int rx, int ry, int bx, int by)
{
    // init
    queue<Ball> waiting_ball;
    waiting_ball.emplace(rx, ry, bx, by, 0);

    // processing
    while (!waiting_ball.empty())
    {
        Ball current_ball = waiting_ball.front();
        waiting_ball.pop();

        if (current_ball.step >= LIMIT_STEP) break; // break point
        else if (Visited[current_ball.rx][current_ball.ry][current_ball.bx][current_ball.by]) continue;

        Visited[current_ball.rx][current_ball.ry][current_ball.bx][current_ball.by] = true;
        for (int dir = 0; dir < MOVING_MAX; ++dir)
        {
            bool is_failed = false;
            bool is_succeeded = false;

            Ball next_ball = { current_ball.rx, current_ball.ry, current_ball.bx, current_ball.by, current_ball.step + 1 };

            // rolling
            while (Map[next_ball.rx + DX[dir]][next_ball.ry + DY[dir]] != '#')
            {
                next_ball.rx += DX[dir];
                next_ball.ry += DY[dir];

                if (Map[next_ball.rx][next_ball.ry] == 'O') is_succeeded = true;
            }
            while (Map[next_ball.bx + DX[dir]][next_ball.by + DY[dir]] != '#')
            {
                next_ball.bx += DX[dir];
                next_ball.by += DY[dir];

                if (Map[next_ball.bx][next_ball.by] == 'O') is_failed = true;
            }

            // overlaped
            if (next_ball.rx == next_ball.bx && next_ball.ry == next_ball.by)
            {
                if (current_ball.rx - DX[dir] == current_ball.bx && current_ball.ry - DY[dir] == current_ball.by)
                {
                    next_ball.bx -= DX[dir];
                    next_ball.by -= DY[dir];
                }
                else
                {
                    next_ball.rx -= DX[dir];
                    next_ball.ry -= DY[dir];
                }
            }
            
            // chk conditions
            if(!is_failed && !Visited[next_ball.rx][next_ball.ry][next_ball.bx][next_ball.by])
            {
                if (is_succeeded) return current_ball.step + 1;
                else waiting_ball.push(next_ball);
            }
        }
    }

    return -1;
}

int main(void)
{
    ios::sync_with_stdio(false);
    //freopen("input.txt", "r", stdin);

    // input
    scanf("%d %d", &N, &M);

    int rx, ry, bx, by;
    for (int i = 0; i < N; ++i)
    {
        char buf[MAP_MAX + 1];
        scanf("%s", buf);

        for (int j = 0; j < M; ++j)
        {
            Map[i][j] = buf[j];
            if (buf[j] == 'R') rx = i, ry = j;
            else if (buf[j] == 'B') bx = i, by = j;
        }
    }

    // processing
    int res = moving_ball(rx, ry, bx, by);
    
    // output
    printf("%d", res);

    return 0;
}

smtsyh 7년 전 4

이 테스트 케이스는 어떨까요

제가 해본 결과로는 7이 맞는것 같은데..

10 10
##########
#R.....#B#
#........#
#........#
#........#
#........#
#........#
#.....#..#
#....#O..#
##########

asd0113 7년 전 1

smtsyh

감사합니다. 해결되었습니다. :)

틀린 부분이 overlaped 부분이 틀렸었네요.

이전에 같은 줄에서 떨어져있던 상태에서 공을 굴렸을 때 겹친 것을 제대로 체킹을 못했네요.

감사합니다.

myth 7년 전 0

위에 알려주신 테스트 케이스는 아무리 봐도 파란색 공이 구멍으로 들어 가서 -1 이 되는 것 같은데요,

어떻게 7이 나오는지 간단한 설명 부탁 드립니다~

sukwoo0711 7년 전 3

@myth

1.오른쪽

2.아래

3.오른쪽

4.위

5.왼쪽

6.아래

7.왼쪽

이 순으로 들어가면 됩니다

algawhat 4년 전 0

진짜 진짜 진짜 감사합니다

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

문제

문제

출처

ICPC

쨰로탈출2 다른 테스트케이스 관련 질문있습니다.

asd0113 7년 전 0

smtsyh 7년 전 4

asd0113 7년 전 1

smtsyh

myth 7년 전 0

sukwoo0711 7년 전 3

algawhat 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말