달이 차오른다, 가자. - 1194번

---

package com.company;

import java.io.*;
import java.util.*;

public class Main {
    static int[][] d = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int answer = -1;

        char[][] arr = new char[N][M];
        boolean[][][] visited = new boolean[64][N][M];  
        // 비트마스킹으로 확인, 열쇠 없을때 000000, a만 가지고 있을때 000001, a랑 b 가지고 있을때 000011 
        
        Node first = null;  // 시작 위치

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                char c = s.charAt(j);
                if (c == '0') {
                    first = new Node(i, j, 0, 0);
                    arr[i][j] = '.';
                } else {
                    arr[i][j] = c;
                }
            }
        }

        Queue<Node> q = new LinkedList<>();
        visited[0][first.x][first.y] = true;    // 시작할때 열쇠 없으므로 0에서 위치 방문 처리
        q.add(first);

        while (!q.isEmpty()) {
            Node node = q.poll();
            if (arr[node.x][node.y] == '1') {   // 탈출하면 종료
                answer = node.count;
                break;
            }

            for (int i = 0; i < 4; i++) {
                int nextX = node.x + d[i][0];
                int nextY = node.y + d[i][1];

                // 현재 열쇠상태로 방문 했거나 벽이면 방문 하지 않음,
                if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < M
                        && !visited[node.k][nextX][nextY] && arr[nextX][nextY] != '#' && !visited[node.k][nextX][nextY]) {
                    char c = arr[nextX][nextY];

                    Node newNode = new Node(nextX, nextY, node.count + 1, node.k);  // 다음 위치

                    // 열쇠 찾으면 비트 연산 | 로 열쇠 추가
                    if (c >= 'a' && c <= 'f') {
                        int x = 1 << c - 'a';
                        newNode.k = x | node.k;
                    } else if (c >= 'A' && c <= 'F') {  // 비트 연산 &로 열쇠를 가지고 있는지 확인
                        int x = 1 << c - 'A';
                        if ((x & node.k) < 1) {
                            continue;
                        }
                    }
                    visited[node.k][nextX][nextY] = true;   // 현재 열쇠 상태로 방문 처리
                    q.add(newNode);
                }
            }
        }
        System.out.println(answer);
    }

    static class Node {
        int x, y, count, k; // x,y : 위치, count : 이동 횟수, k : key 상태 (비트로 가짐)

        public Node(int x, int y, int count, int k) {
            this.x = x;
            this.y = y;
            this.count = count;
            this.k = k;
        }
    }
}