import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class NgonLua {
static int[][] visit;
static char[][] mang;
static int row, col;
static int xlua, ylua, xjoe, yjoe;
static int start, end;
static int[] quex;
static int[] quey;
static int[] dx = { 0, 0, - 1, 1 };
static int[] dy = { -1, 1, 0, 0 };
static void push(int x, int y) {
quex[start] = x;
quey[start] = y;
start++;
}
static boolean isEmpty() {
if (start == end) {
return true;
}
return false;
}
static void BFS(int x, int y) {
start = end = 0;
push(x, y);
visit[x][y] = 1;
while (!isEmpty()) {
int a = quex[end];
int b = quey[end];
end++;
for (int i = 0; i < 4; i++) {
int nx = a + dx[i];
int ny = b + dy[i];v
if (nx >= 0 && nx < row && ny >= 0 && ny < col && mang[nx][ny]!='#') {
if (visit[a][b] + 1 < visit[nx][ny]) {
visit[nx][ny] = visit[a][b] + 1;
push(nx, ny);
}
}
}
}
}
static int BFS1(int x, int y) {
start = end = 0;
push(x, y);
visit[x][y] = 1;
while (!isEmpty()) {
int a = quex[end];
int b = quey[end];
end++;
if( a== row-1 || a==0 || b== col-1 || b==0){
return visit[a][b];
}
for (int i = 0; i < 4; i++) {
int nx = a + dx[i];
int ny = b + dy[i];
if (nx >= 0 && nx < row && ny >= 0 && ny < col && mang[nx][ny]!='#') {
if (visit[a][b] + 1 < visit[nx][ny]) {
visit[nx][ny] = visit[a][b] + 1;
push(nx, ny);
}
}
}
}
return -1;
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("ngonlua.txt"));
Scanner sc = new Scanner(System.in);
int T=sc.nextInt();
for (int tc = 1; tc <=T; tc++) {
row = sc.nextInt();
col = sc.nextInt();
mang = new char[row][col];
quex = new int[100000];
quey = new int[100000];
visit = new int[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
visit[i][j] = 100000;
}
}
for (int i = 0; i < row; i++) {
String s = sc.next();
for (int j = 0; j < col; j++) {
mang[i][j] = s.charAt(j);
}
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (mang[i][j] == 'J') {
xjoe = i;
yjoe = j;
}
if (mang[i][j] == 'F') {
xlua = i;
ylua = j;
}
}
}
if( xjoe== row-1 || xjoe==0 || yjoe== col-1 ||yjoe==0){
System.out.println(1);
}else{
BFS( xlua, ylua);
int x=BFS1(xjoe, yjoe);
if( x==-1){
System.out.println("IMPOSSIBLE");
}else{
System.out.println(x);
}
}
}}}
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.