항 전 1429 승리 대도 망 수색

승리 대도 망 (계속)
Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 7156    Accepted Submission(s): 2470
Problem Description
이 그 나 티 우 스 는 다시 마왕 에 게 잡 혀 갔다.
이번 마왕 은 지난번 의 교훈 을 얻 었 습 니 다. Ignatius 를 n * m 의 지하 감옥 에 가 두 었 고 지하 감옥 어 딘 가 에 자물쇠 가 달 린 문 을 설 치 했 습 니 다. 열 쇠 는 지하 감옥 의 다른 어 딘 가 에 숨 겼 습 니 다.처음에 Ignatius 는 (sx, sy) 의 위치 에 갇 혔 고 지하 감옥 을 떠 난 문 은 (ex, ey) 의 위치 에 있 었 다.Ignatius 는 매 분 한 좌표 에서 인접 한 네 개의 좌표 중 하나 로 만 갈 수 있다.마왕 은 t 분 에 한 번 씩 지하 감옥 을 시찰 하 는데, Ignatius 가 제자리 에 없 는 것 을 발견 하면 그 를 데 리 고 돌아 갑 니 다.몇 차례 의 시 도 를 거 쳐 Ignatius 는 지하 감옥 전 체 를 그 렸 다.이제 다시 성공 적 으로 도망 갈 수 있 을 지 계산 해 주세요.마왕 이 다음 시찰 을 하기 전에 출구 로 나 가면 지하 감옥 을 떠 나 더 라 도 마왕 이 돌아 올 때 마침 출구 에 도착 하거나 출구 에 도착 하지 않 으 면 도망 에 실패 하 는 셈 이다.
 
Input
각 조 의 테스트 데이터 의 첫 줄 에는 세 개의 정수 n, m, t (2 < = n, m < 20, t > 0) 가 있다.다음 n 행 m 는 지하 감옥 의 지도 입 니 다. 그 중에서 다음 과 같 습 니 다.
대표 로
* 대표 벽
@ Ignatius 를 대표 하 는 시작 위치
↑ 지하 감옥 을 대표 하 는 출구
A - J 는 자물쇠 가 달 린 문 을 대표 하고 해당 하 는 열 쇠 는 각각 a - j 이다.
a - j 는 열 쇠 를 대표 하고 대응 하 는 문 은 각각 A - J 이다.
각 그룹의 테스트 데이터 사이 에 빈 줄 이 하나 있다.
 
Output
각 조 의 테스트 데 이 터 를 대상 으로 탈출 에 성공 할 수 있다 면 출력 은 몇 분 이 걸 려 야 떠 날 수 있 습 니까? 그렇지 않 으 면 출력 - 1.
 
Sample Input

   
   
   
   

    
    
    
    4 5 17
@A.B.
a*.*.
*..*^
c..b*

4 5 16
@A.B.
a*.*.
*..*^
c..b*
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    16
-1
   
   
   
   

 
Author
LL
검색 문 제 는 일반적으로 우리 가 직접 문제 의 뜻 을 이해 한 후에 샘플 을 본다.
사실 이 문제 의 의 미 는 명확 하지 않다. 왜냐하면 두 번 째 그림 은 분명히 20 시간 동안 출구 를 나 갈 수 있 지만 문제 의 의식 은 안 된다 는 것 이다............................................
여기 서 우 리 는 먼저 첫 번 째 문 제 를 분석한다.
질문 .
a  *  .
*   *  .
문 제 는 우선 우리 가 먼저 열 쇠 를 가 져 온 다음 에 뒤 돌아 서 문 을 열 어야 합 니 다. 여기 에는 반복 되 는 경로 가 있 습 니 다 @. 이 길 을 반복 할 때 두 번 이곳 을 가 는 차이 가 매우 뚜렷 합 니 다. 첫 번 째 는 열쇠 가 없 었 지만 두 번 째 는 열쇠 가 있 었 습 니 다.차이 점 은 바로 여기에 있 습 니 다. 그래서 우 리 는 이 길 을 걸 었 는 지 판단 하 는 배열 vis 를 3 차원 으로 해 야 합 니 다.

int vis[21][21][1025];//              ，             .....       

지금 되 돌아 오 는 문 제 를 다 처 리 했 는데, 여기 또 하나의 어 려 운 점 은 우리 가 문 을 여 는 열쇠 가 있 는 지 없 는 지 를 어떻게 판단 하 는 것 입 니까?
여기 서 비트 연산 과 관련 된 것 이 있 습 니 다. (나 는 비트 연산 의 이 부분 을 잘 묘사 하지 못 하기 때문에 아래 의 이 상세 한 설명 은 전재 한 것 입 니 다)http://bluereader.org/article/73263006< - 유래.
문 이 열 릴 지 여 부 를 판단 할 때 열쇠 와 문 번호 로 '&' - '예 를 들 어 10001000100000 & 000100000 = 1 설명 은' A '+ 6 이 문 을 열 수 있다.
열 쇠 를 만나면 이 열 쇠 를 넣 어야 한다.열쇠 꾸러미 에 열 쇠 를 넣 으 면 '|' -> 예 를 들 어 10001000100010 | 0000010000 = 1000110010;’직렬  만약 우리 가 열 쇠 를 만 났 다 면, 상응하는 열 쇠 를 넣 는 조작 이 있어 야 한다.

                if(a[nex.x][nex.y]>='a'&&a[nex.x][nex.y]<='j')
                {
                    int temp=a[nex.x][nex.y]-'a';
                    if((nex.key&(1<<temp))==0)//   （          ）
                    nex.key+=(1<<temp);（  ）
                }

상대 적 으로 만약 에 우리 가 문 을 만 났 고 열쇠 가 있 는 상황 에서 우 리 는 통과 해 야 한다. 그렇지 않 으 면 이 문 을 걸 을 수 없다.
4. 567913. 가장 중요 한 두 가지 문 제 를 해결 한 다음 에 완전한 코드 를 붙인다.

                if(a[nex.x][nex.y]>='A'&&a[nex.x][nex.y]<='J')
                {
                    int temp=a[nex.x][nex.y]-'A';
                    if((nex.key&(1<<temp))==0)//（            ）
                    continue;//（       ）
                }