2017.8.1 퍼 즐 도 내 추 필 시험 문제 (4) - 미로 길 찾기 (상태 압축 + BFS)

제목 은 탐험가 가 바닥 의 미로 에 갇 혀 있다 고 가정 하고 현재 위치 에서 미로 출구 로 가 는 경 로 를 찾 아야 한다.미 로 는 2 차원 행렬 로 이 루어 질 수 있 고, 어떤 부분 은 벽 이 며, 어떤 부분 은 길이 다.미로 속 에는 길 도 있 고 문 도 있 습 니 다. 모든 문 은 미로 어 딘 가 에 그 에 맞 는 열쇠 가 있 습 니 다. 열 쇠 를 먼저 받 아야 문 을 열 수 있 습 니 다.탐험가 가 곤경 에서 벗 어 나 는 가장 짧 은 경 로 를 찾 을 수 있 도록 알고리즘 을 설계 하 세 요.앞에서 말 한 바 와 같이 미 로 는 2 차원 행렬 을 통 해 표 시 된 것 으로 각 요소 의 값 의 의 미 는 0 - 벽, 1 - 길, 2 - 탐험가 의 시작 위치, 3 - 미로 의 출구, 대문자 - 문, 소문 자 - 대문자 가 대표 하 는 문 에 대응 하 는 열쇠 이다.미 로 를 설명 하 는 지 도 를 입력 하고 2 차원 행렬 로 표시 합 니 다.첫 번 째 줄 은 행렬 의 줄 수 와 열 수 M 과 N 뒤의 M 줄 이 행렬 의 데이터 이 고 각 줄 은 행렬 의 한 줄 (중간 에 빈 칸 이 없 음) 에 대응 합 니 다.M 과 N 은 모두 100 을 넘 지 않 고 문 은 10 개 를 넘 지 않 는 다.입력 예 55 02111 01a0A 01003 01001 01111 출력 예 7 문제 사고: 이 문 제 를 풀 기 전에 BFS 를 알 지 못 했 기 때문에 교과 서 를 빨리 훑 어 보 았 습 니 다. 여기 서 가장 짧 은 거 리 를 구 했 습 니 다. 게다가 문의 수량 이 10 개 를 초과 하지 않 기 때문에 직접 폭력 BFS 를 사용 하고 열 쇠 를 가 진 상 태 를 기록 해 야 합 니 다.그래서 상태 압축 을 사용 하여 이 진수 로 열쇠 상 태 를 표시 합 니 다.BFS 에 앞서 초기 상태 설정 을 제시 합 니 다. 여 기 는 열쇠 라 는 개념 이 있 기 때문에 문 제 는 가 는 과정 에서 열쇠 정 보 를 기록 하 는 방법 으로 바 뀌 었 습 니 다. 그래서 여 기 는 하나의 상태 압축 법 을 사용 하여 하나의 숫자 로 어떤 열쇠 가 있 는 지 를 대표 합 니 다. 즉, 이 수의 2 진 표 시 는 i 위 가 1 인 것 은 a + i 열쇠 가 있 는 것 을 대표 합 니 다. 그렇지 않 으 면 없습니다.미로 의 점 마다 1024 개의 상태 가 있 는 셈 이다.다음은 BFS 구현 코드 를 드 립 니 다.

int n,m,sx,sy,ex,ey;
char g[1024][1024];
int use[120][120][1400];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
struct node
{
    int x,y,k;
};

int bfs()
{
    memset(use,0xff,sizeof(use));
    queueq;
    node t;
    t.x=sx;
    t.y=sy;
    t.k=0;
    use[t.x][t.y][t.k]=0;
    q.push(t);
    while(!q.empty())
    {
        t = q.front();
        q.pop();
        //printf("%d %d %d %d
",t.x,t.y,t.k,use[t.x][t.y][t.k]);
        if(t.x==ex&&t.y==ey) return use[t.x][t.y][t.k];
        for(int i=0;i<4;i++)//    
        {
            node k;//        
            k.x = t.x + dx[i];
            k.y = t.y + dy[i];
            k.k = t.k;
            if(k.x<0||k.x>=n||k.y<0||k.y>=m||g[k.x][k.y]=='0') continue;//        
            if(g[k.x][k.y]>='a'&&g[k.x][k.y]<='z')
            {
                k.k = k.k|(1<.x][k.y]-'a'));//         
            }
            if(g[k.x][k.y]>='A'&&g[k.x][k.y]<='Z')
            {
                int p = k.k&(1<.x][k.y]-'A'));//        
                if(p==0) continue;//            
            }
            if(use[k.x][k.y][k.k]==-1||use[k.x][k.y][k.k]>use[t.x][t.y][t.k]+1)//           BFS，          
            {
                use[k.x][k.y][k.k]=use[t.x][t.y][t.k]+1;
                q.push(k);
            }
        }
    }
    return -1;
}

BFS + 상태 압축 이 있 으 면 주 함 수 를 쓰 면 바로 AC 가 됩 니 다.주 함수

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i"%s",g[i]);
        for(int j=0;j<m;j++)
        {
            if(g[i][j]=='2') {sx=i;sy=j;}//    
            if(g[i][j]=='3') {ex=i;ey=j;}//    
        }
    }
    printf("%d
",bfs());
    return 0;
}