133 lines
3.4 KiB
Java
133 lines
3.4 KiB
Java
import java.util.*;
|
|
|
|
class Pair {
|
|
int x, y;
|
|
|
|
Pair(int x, int y) {
|
|
this.x = x;
|
|
this.y = y;
|
|
}
|
|
}
|
|
|
|
public class _9328 {
|
|
static int h, w;
|
|
|
|
static Character[][] MAP;
|
|
static Boolean[] key;
|
|
|
|
static boolean[][] visited;
|
|
static Queue<Pair> qu;
|
|
static Queue<Pair>[] door;
|
|
|
|
static int[] dx = {1, -1, 0, 0};
|
|
static int[] dy = {0, 0, 1, -1};
|
|
|
|
static boolean isImpossible(int x, int y) {
|
|
return (0 > x || x >= w + 2 || 0 > y || y >= h + 2) || visited[y][x] || MAP[y][x] == '*';
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
Scanner sc = new Scanner(System.in);
|
|
|
|
int T = Integer.parseInt(sc.nextLine());
|
|
int[] res = new int[T];
|
|
|
|
for(int t=0; t<T; t++) {
|
|
int[] info = Arrays.stream(sc.nextLine().split(" "))
|
|
.mapToInt(Integer::parseInt)
|
|
.toArray();
|
|
|
|
h = info[0];
|
|
w = info[1];
|
|
|
|
MAP = new Character[h+2][w+2];
|
|
|
|
for(int i=0; i<h+2; i++) {
|
|
for(int j=0; j<w+2; j++) {
|
|
if(i == 0 || i == h + 1) MAP[i][j] = '.';
|
|
else if(j == 0 || j == w + 1) MAP[i][j] = '.';
|
|
}
|
|
}
|
|
|
|
for(int y=1; y<h+1; y++) {
|
|
String line = sc.nextLine();
|
|
|
|
for(int x=1; x<w+1; x++) {
|
|
MAP[y][x] = line.charAt(x-1);
|
|
}
|
|
}
|
|
|
|
key = new Boolean[26];
|
|
Arrays.fill(key, false);
|
|
String keyInfo = sc.nextLine();
|
|
|
|
for(int i=0; i<keyInfo.length(); i++) {
|
|
if(keyInfo.charAt(i) == '0') break;
|
|
|
|
key[keyInfo.charAt(i) - 'a'] = true;
|
|
}
|
|
|
|
qu = new LinkedList<>();
|
|
|
|
door = new Queue[26];
|
|
for(int i=0; i<26; i++) door[i] = new LinkedList<>();
|
|
|
|
visited = new boolean[h+2][w+2];
|
|
|
|
qu.add(new Pair(0, 0));
|
|
visited[0][0] = true;
|
|
|
|
int material = 0;
|
|
|
|
while(!qu.isEmpty()) {
|
|
Pair curr = qu.poll();
|
|
int cx = curr.x, cy = curr.y;
|
|
|
|
for(int i=0; i<4; i++) {
|
|
int nx = cx + dx[i], ny = cy + dy[i];
|
|
|
|
if(isImpossible(nx, ny)) continue;
|
|
|
|
visited[ny][nx] = true;
|
|
|
|
Character location = MAP[ny][nx];
|
|
|
|
if(Character.isLowerCase(location)) {
|
|
key[location - 'a'] = true;
|
|
qu.add(new Pair(nx, ny));
|
|
|
|
while(!door[location - 'a'].isEmpty()) {
|
|
qu.add(door[location - 'a'].poll());
|
|
}
|
|
}
|
|
|
|
else if(Character.isUpperCase(location)) {
|
|
|
|
if(!key[location - 'A']) {
|
|
door[location - 'A'].add(new Pair(nx, ny));
|
|
}
|
|
|
|
else {
|
|
qu.add(new Pair(nx, ny));
|
|
}
|
|
}
|
|
|
|
else {
|
|
qu.add(new Pair(nx, ny));
|
|
if(location == '$') material++;
|
|
}
|
|
}
|
|
}
|
|
|
|
res[t] = material;
|
|
|
|
}
|
|
|
|
sc.close();
|
|
|
|
for (int n : res) {
|
|
System.out.println(n);
|
|
}
|
|
}
|
|
}
|