글 읽기 - bfs와 비트마스크를 이용하여 풀었는데.. 왜 안되는지 잘모르겠습니다.

kioio5 6년 전 2

비트마스크를 이용하여 풀었습니다.

get_key(현재 가지고 있는 키, 얻을 키) : 쉬프트 연산을 통해서 새로운 키 뭉치를 리턴함.

inspect_door(현재 가지고 있는 키, 검사할 문) : 검사할 문에 해당하는 키를 가지고 있는지 엔드 연산을 통해 검사.

최단 경로를 구하는 것이기 때문에 bfs를 이용하여 도착점을 발견한다면 최적의 해이므로, 바로 리턴하게 했고

만약 갈 수 있는 길이 없다면 -1을 리턴하게 했습니다.

도저히 모르겠습니다...ㅠㅠㅠ 고수님들 도움좀 주시면 감사하겠습니다.

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

#define MAX_SIZE 51

using namespace std;

typedef pair<int, int> p;

int n, m;
char map[MAX_SIZE][MAX_SIZE];

int sx, sy;
int ex, ey;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

bool visit[1<<6][MAX_SIZE][MAX_SIZE];

void input()
{
    scanf("%d %d", &m, &n);
    getchar();
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            map[i][j] = getchar();
            if(map[i][j] == '0') sx = i, sy = j;
            else if(map[i][j] == '1') ex = i, ey = j;
        }
        getchar();
    }
}

int get_key(int now, char key)
{
    int add_value = (1 << (key - 'a'));

    return add_value | now;
}

bool inspect_door(int now, char door)
{
    int add_value = (1 << (door - 'A'));

    return add_value & now;
}

int bfs()
{
    queue<pair<p, p> > q;
    q.push(make_pair(make_pair(sx, sy), make_pair(0, 0)));

    while(!q.empty())
    {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int weight = q.front().second.first;
        int key = q.front().second.second;

        q.pop();

        if(x == ex && y == ey) return weight;

        if(visit[key][x][y]) continue;
        visit[key][x][y] = 1;

        for(int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || ny < 0 || nx >= m || ny >= n || visit[key][nx][ny] || map[nx][ny] == '#') continue;

            if(map[nx][ny] >= 'A' && map[nx][ny] <= 'F')
            {
                if(inspect_door(key, map[nx][ny]))
                    q.push(make_pair(make_pair(nx, ny), make_pair(weight + 1, key)));

                continue;
            }

            int nk = key;

            if(map[nx][ny] >= 'a' && map[nx][ny] <= 'f') nk = get_key(key, map[nx][ny]);

            q.push(make_pair(make_pair(nx, ny), make_pair(weight + 1, nk)));
        }
    }

    return -1;
}


int main()
{

    input();
    printf("%d\n", bfs());

    return 0;
}

ljk0411jg 6년 전 2

1이 여러개가 나올수있는데 32번째 줄이랑 66번째 줄을 보면 1이 한군데에서만 나오는 조건으로 설정해놔서 틀리는거같네용

kioio5 6년 전 0

@ljk0411jg

....이런........

1이 여러군데일 수 있었군요..

고치니까 바로 맞네요 ㅎㅎ.....

예리함에 박수를 드립니다!!

감사합니다!!!!!

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

문제

문제

출처

ICPC

bfs와 비트마스크를 이용하여 풀었는데.. 왜 안되는지 잘모르겠습니다.

kioio5 6년 전 2

ljk0411jg 6년 전 2

kioio5 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말