백준 1194 달이차오른다, 가자 (자바)

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class algo_1194_김어진 {
	static int N;
	static int M;
	static int[] dx = {-1,0,1,0};
	static int[] dy = {0,1,0,-1};
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("input.txt"));

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine()," ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		char[][] board = new char[N][M];
		boolean[][][] check=new boolean[N][M][1<<7];
		for (int i = 0; i < N; i++) {
			board[i] = br.readLine().toCharArray();
		}
		int[] now =new int[2];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(board[i][j]=='0') {
					now[0]= i;
					now[1]=j;
				}
			}
		}
		
		Queue<Node> q = new LinkedList<Node>();
		Node nd = new Node(now[0],now[1],0,1);
		check[now[0]][now[1]][1]=true;
		q.add(nd);
		while(!q.isEmpty()) {
			Node nowNode =q.poll();
			int x = nowNode.x;
			int y = nowNode.y;
			int cost = nowNode.cost;
			int keys = nowNode.keys;
			
			if(board[x][y]=='1') {
				System.out.println(nowNode.cost);
				return;
			}
			
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if(nx>=0 && nx < N && ny>=0 && ny<M && board[nx][ny]!='#' && !check[nx][ny][keys]){
					char value=board[nx][ny];
					boolean chk=true;
					if('a'<=value && value<='f') {
						Node nnd = new Node(nx,ny,cost+1,addKey(keys, value));
						check[nx][ny][nnd.keys]=true;
						q.add(nnd);
						continue;
					}
					else if('A'<=value && value<='F') {
						if(!keyCheck(keys,value)) continue;
						
					}
				
					q.add(new Node(nx,ny,cost+1,keys));
					check[nx][ny][keys]=true;
					
					
				}
			}
		}
		System.out.println(-1);
	}
	public static int addKey(int key, char x){
		if(!keyCheck(key,x)) {
			key+=Math.pow(2,x-'a'+1);
			
		}
		return key;

	}
	public static boolean keyCheck(int key, char x) {
		key = key>>(x-'A'+1) & 1;
		if(key==1) return true;
		else return false;
	}
	static class Node{


		int x;
		int y;
		int cost;
		int keys;
		
		public Node(int x, int y, int cost, int keys) {
			super();
			this.x = x;
			this.y = y;
			this.cost = cost;
			this.keys = keys;
		}
		

		
	}
}