CLLEXO.java

import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
 
class CLLEXO {
    static char arr[][];
    static int n, m;
    static boolean reach[][], visited[][];
 
    static boolean check(int x, int y) {
        if (x < n && y < m && reach[x][y])
            return true;
        return false;
    }
 
    static boolean check1(int x, int y) {
        if (x == 0 && y == 0)
            return true;
        if (x < n && y < m && x >= 0 && y >= 0) {
            return true;
        }
        return false;
    }
 
    public static void main(String[] args) throws IOException {
        FastReader in = new FastReader(System.in);
        StringBuilder sb = new StringBuilder();
        int i, j;
        int t = in.nextInt();
        while (t-- > 0) {
            n = in.nextInt();
            m = in.nextInt();
            arr = new char[n][m];
            for (i = 0; i < n; i++) {
                arr[i] = in.next().toCharArray();
            }
 
            reach = new boolean[n][m];
            reach[n - 1][m - 1] = true;
            for (i = n - 1; i >= 0; i--) {     // bottom-up dp from arr[n][m]
                for (j = m - 1; j >= 0; j--) {
                    if (arr[i][j] != '#' && (check(i + 1, j) || check(i, j + 1)))
                        reach[i][j] = true;
                }
            }
 
            HashSet<List<Integer>> set = new HashSet<>();
            sb.append(arr[0][0]);
            set.add(Arrays.asList(0, 0));
            for (i = 1; i <= n + m - 2; i++) {      // BFS
                HashSet<List<Integer>> set1 = new HashSet<>();
                int ch = 'z';
                for (List<Integer> s : set) {
                    int x = s.get(0);
                    int y = s.get(1);
                    if (check1(x + 1, y) && reach[x + 1][y])
                        ch = Math.min(ch, arr[x + 1][y]);
                    if (check1(x, y + 1) && reach[x][y + 1])
                        ch = Math.min(ch, arr[x][y + 1]);
                }
                for (List<Integer> s : set) {
                    int x = s.get(0);
                    int y = s.get(1);
                    if (check1(x + 1, y) && reach[x + 1][y] && arr[x + 1][y] == ch)
                        set1.add(Arrays.asList(x + 1, y));
                    if (check1(x, y + 1) && reach[x][y + 1] && arr[x][y + 1] == ch)
                        set1.add(Arrays.asList(x, y + 1));
                }
                set = set1;
                sb.append((char) ch);
            }
 
            sb.append("\n");
        }
 
        System.out.print(sb);
    }
}
 
 
class FastReader {
 
    byte[] buf = new byte[2048];
    int index, total;
    InputStream in;
 
    FastReader(InputStream is) {
        in = is;
    }
 
    int scan() throws IOException {
        if (index >= total) {
            index = 0;
            total = in.read(buf);
            if (total <= 0) {
                return -1;
            }
        }
        return buf[index++];
    }
 
    String next() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        StringBuilder sb = new StringBuilder();
        for (; c > 32; c = scan()) {
            sb.append((char) c);
        }
        return sb.toString();
    }
 
    int nextInt() throws IOException {
        int c, val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }
 
    long nextLong() throws IOException {
        int c;
        long val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }
}