[Baekjoon] #9328 열쇠

 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Location{
	int x;
	int y;
	
	public Location(int x, int y) {
		// TODO Auto-generated constructor stub
		this.x = x;
		this.y = y;
	}
}

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		
		int tc = sc.nextInt();
		
		for(int testcase=0;testcase<tc;testcase++){
			
			int h = sc.nextInt();
			int w = sc.nextInt();
			int cnt =0;
			boolean flag = false; // 새로운 키를 획득하는지에 따른 여부
			
			char[][] map = new char[h][w];
			int[][] visit = new int[h][w];
			Queue<Location> q = new LinkedList<>();
			ArrayList<Character> ar = new ArrayList<>();
			
			for(int i=0;i<h;i++){
				String str = sc.next();
				char[] c = str.toCharArray();
				for(int j=0;j<w;j++){
					map[i][j] = c[j];
					//charAt 과 toCharArray 속도 비교
				}
			}
			
			String strKey = sc.next();
			for(int i=0;i<strKey.length();i++){
				ar.add(strKey.charAt(i));
			}
			
			while(!flag){
				
				flag = true;
				
				for(int i=0;i<h;i+=h-1){
					for(int j=0;j<w;j++){
						if(map[i][j] == '.'){
							q.offer(new Location(i, j));
						}else if('a'<=map[i][j] && map[i][j] <= 'z'){
							ar.add(map[i][j]);
							map[i][j] = '.';
							flag = false;
							q.offer(new Location(i, j));
						}else if('A'<=map[i][j] && map[i][j] <= 'Z'){
							for(int k=0;k<ar.size();k++){
								if(map[i][j] == ar.get(k)-32){
									map[i][j] = '.';
									q.offer(new Location(i, j));
								}
							}
						}else if(map[i][j] == '$'){
							cnt++;
							map[i][j] = '.';
						}
					}
				}
				
				for(int i=0;i<w;i+=w-1){
					for(int j=0;j<h;j++){
						if(map[j][i] == '.'){
							q.offer(new Location(j, i));
						}else if('a'<=map[j][i] && map[j][i] <= 'z'){
							ar.add(map[j][i]);
							map[j][i] = '.';
							flag = false;
							q.offer(new Location(j, i));
						}else if('A'<=map[j][i] && map[j][i] <= 'Z'){
							for(int k=0;k<ar.size();k++){
								if(map[j][i] == ar.get(k)-32){
									map[j][i] = '.';
									q.offer(new Location(j, i));
								}
							}
						}else if(map[j][i] == '$'){
							cnt++;
							map[j][i] = '.';
						}
					}
				}
				
				//System.out.println("=== while Start ===");
				while(!q.isEmpty()){
					
					
					int[] xx = {-1,0,1,0};
					int[] yy = {0,1,0,-1};
									
					int x = q.peek().x;
					int y = q.poll().y;
					
					//System.out.println("-> 현재 위치  : map["+x+"]["+y+"]");
					
					for(int i=0;i<4;i++){
						
						int ax = x+xx[i];
						int ay = y+yy[i];
						
						if(ax>=0 && ay>=0 && ax<h && ay< w){
							if(map[ax][ay] =='.' && visit[ax][ay] == 0){
								visit[ax][ay] = 1;
								//System.out.println("빈곳 체크 : map["+ax+"]["+ay+"]");
								q.offer(new Location(ax, ay));
							}else if('a'<=map[ax][ay] && map[ax][ay] <='z' && visit[ax][ay] == 0){
								ar.add(map[ax][ay]);
								//System.out.println("열쇠 획득 : map["+ax+"]["+ay+"] : "+map[ax][ay]);
								map[ax][ay] = '.';
								visit[ax][ay] = 1;
								flag = false;
								q.offer(new Location(ax, ay));
							}else if('A'<=map[ax][ay] && map[ax][ay]<='Z' && visit[ax][ay] == 0){
								for(int aa = 0; aa<ar.size();aa++){
									if(map[ax][ay] == ar.get(aa)-32){
										map[ax][ay] = '.';
										visit[ax][ay] = 1;
										//System.out.println("문 체크 : map["+ax+"]["+ay+"]");
										q.offer(new Location(ax, ay));
									}
								}
							}else if(map[ax][ay] == '$' && visit[ax][ay] == 0){
								visit[ax][ay] = 1;
								cnt++;
								map[ax][ay] = '.';
								//System.out.println("★문서 체크 : map["+ax+"]["+ay+"]");
								q.offer(new Location(ax, ay));
							}else if(map[ax][ay] == '*' && visit[ax][ay] == 0){
								//System.out.println("벽 체크 : map["+ax+"]["+ay+"]");
								continue;
							}
						}
					}
				}
				
				
				for(int i=0;i<h;i++){
					for(int j=0;j<w;j++){
						visit[i][j] = 0;
					}
				}
				
			}
			
			
				
			
			System.out.println(cnt);
			
		}
		
	}
}