import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class Main {
static class Point {
public int row;
public int col;
public Point(int row, int col) {
this.row = row;
this.col = col;
}
}
public static int rowMatrix = 0;
public static int colMatrix = 0;
public static boolean isValid(int row, int col, String[]matrix) {
return row >= 0 && row < rowMatrix && col >= 0 && col < colMatrix && matrix[row].charAt(col) == '.';
}
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tk = new StringTokenizer(br.readLine());
int tc = Integer.parseInt(tk.nextToken());
for(int i = 0; i < tc; i ++) {
tk = new StringTokenizer(br.readLine());
int m = Integer.parseInt(tk.nextToken());
int n = Integer.parseInt(tk.nextToken());
rowMatrix = m;
colMatrix = n;
/*
// Read input like this will lead to TLE!!!
char[][] matrix = new char[m][n];
for(int j = 0;j< m; j ++) {
int value = 0;
int run = 0;
while((value = br.read()) != 10){ // 10 is endLine
matrix[j][run] = (char)value;
run++;
}
}*/
// This one otherwise is OK!
String[] matrix = new String[m];
for(int j = 0; j < m; j ++) {
matrix[j] = br.readLine();
}
int cnt = 0;
//List contains 2 coordinate of matrix entries
ArrayList<Integer> coordinate = new ArrayList<>();
for(int j = 0; j < m; j ++) {
for(int k = 0; k < n; k ++) {
if((j == 0 || j == m-1 || k == 0 || k == n-1) && matrix[j].charAt(k) == '.') {
cnt++;
coordinate.add(j);
coordinate.add(k);
}
}
}
if(cnt == 2) {
int rowSource = coordinate.get(0);
int colSource = coordinate.get(1);
int rowDes = coordinate.get(2);
int colDes = coordinate.get(3);
boolean[][]visited = new boolean[m][n];
visited[rowSource][colSource] = true;
Queue<Point> q = new LinkedList<>();
q.add(new Point(rowSource, colSource));
int[] dx = {-1,1,0,0};
int[] dy = {0,0,-1,1};
whileLoop:
while(!q.isEmpty()) {
Point v = q.poll();
int headr = v.row;
int headc = v.col;
for(int j = 0; j < 4; j ++) {
int tempr = headr + dx[j];
int tempc = headc + dy[j];
if(isValid(tempr, tempc, matrix) && !visited[tempr][tempc]) {
visited[tempr][tempc] = true;
if(tempr == rowDes && tempc == colDes) {
break whileLoop;
}
q.add(new Point(tempr, tempc));
}
}
}
if(visited[rowDes][colDes]) System.out.println("valid");
else System.out.println("invalid");
} else {
System.out.println("invalid");
}
}
br.close();
}
}
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.