Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- /**
- *
- * @author Alexander
- */
- public class Maze {
- /**
- * @param args the command line arguments
- */
- public static void main(String[] args){
- Scanner input = new Scanner(System.in);
- int tcase = input.nextInt();
- for (int i = 0;i<tcase;i++){
- int rows = input.nextInt();
- int columns = input.nextInt();
- char [][] maze = new char[rows][columns];
- input.nextLine();
- for (int r = 0;r<rows;r++){
- String temp = input.nextLine();
- for (int c = 0;c<columns;c++){
- maze[r][c] = temp.charAt(c);
- }
- }
- Queue <Integer> row = new LinkedList();
- Queue <Integer> column = new LinkedList();
- int [][] px = new int [rows][columns];
- int [][] py = new int [rows][columns];
- boolean [][] visited = new boolean[rows][columns];
- visited[0][0] = true;
- row.add(0);
- column.add(0);
- int count = 1;
- while (!row.isEmpty()){
- int r = row.poll();
- int c = column.poll();
- if (maze[r][c]=='+'){
- if (r>0&&maze[r-1][c]!='*'&&!visited[r-1][c]){
- visited[r-1][c] = true;
- py[r-1][c] = r;
- px[r-1][c] = c;
- row.add(r-1);
- column.add(c);
- }
- if (r<rows-1&&maze[r+1][c]!='*'&&!visited[r+1][c]){
- visited[r+1][c] = true;
- py[r+1][c] = r;
- px[r+1][c] = c;
- row.add(r+1);
- column.add(c);
- }
- if (c>0&&maze[r][c-1]!='*'&&!visited[r][c-1]){
- visited[r][c-1] = true;
- py[r][c-1] = r;
- px[r][c-1] = c;
- row.add(r);
- column.add(c-1);
- }
- if (c<columns-1&&maze[r][c+1]!='*'&&!visited[r][c+1]){
- visited[r][c+1] = true;
- py[r][c+1] = r;
- px[r][c+1] = c;
- row.add(r);
- column.add(c+1);
- }
- }
- else if(maze[r][c]=='-'){
- if (c>0&&maze[r][c-1]!='*'&&!visited[r][c-1]){
- visited[r][c-1] = true;
- py[r][c-1] = r;
- px[r][c-1] = c;
- row.add(r);
- column.add(c-1);
- }
- if (c<columns-1&&maze[r][c+1]!='*'&&!visited[r][c+1]){
- visited[r][c+1] = true;
- py[r][c+1] = r;
- px[r][c+1] = c;
- row.add(r);
- column.add(c+1);
- }
- }
- else if(maze[r][c]=='|'){
- if (r>0&&maze[r-1][c]!='*'&&!visited[r-1][c]){
- visited[r-1][c] = true;
- py[r-1][c] = r;
- px[r-1][c] = c;
- row.add(r-1);
- column.add(c);
- }
- if (r<rows-1&&maze[r+1][c]!='*'&&!visited[r+1][c]){
- visited[r+1][c] = true;
- py[r+1][c] = r;
- px[r+1][c] = c;
- row.add(r+1);
- column.add(c);
- }
- }
- }
- /*for (int r = 0;r<rows;r++){
- for (int c = 0;c<columns;c++){
- if (c==columns-1){
- System.out.println(px[r][c]);
- }
- else {
- System.out.print(px[r][c] + " ");
- }
- }
- }for (int r = 0;r<rows;r++){
- for (int c = 0;c<columns;c++){
- if (c==columns-1){
- System.out.println(py[r][c]);
- }
- else {
- System.out.print(py[r][c] + " ");
- }
- }
- }*/
- if (visited[rows-1][columns-1]){
- int y = rows-1;
- int x = columns-1;
- while(!(y==0&&x==0)){
- int tempx = x;
- int tempy = y;
- x = px[tempy][tempx];
- y = py[tempy][tempx];
- count++;
- }
- System.out.println(count);
- }
- else {
- System.out.println("-1");
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement