Алгоритм Лабиринта тайм-аут на более сложных входах - PullRequest
Новая
       8

Алгоритм Лабиринта тайм-аут на более сложных входах

0 голосов
/ 06 декабря 2018

Это мой алгоритм решения лабиринтов, в котором System.in вводится как 

2
2 3
S..
..B
5 5
S#...
.#...
..#..
.#...
.#..B

Первая строка - это число случаев, вторая строка - это размеры, а следующие (высота) - это строки.лабиринт.Мой код прекрасно работает с этим, но когда я отправляю его через онлайн-компилятор, который использует тестовые данные судьи, он истекает при более длинном вводе. 

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class BeanMaze {

    public static void main(String[] args) throws FileNotFoundException {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in = new Scanner(System.in);
        int numLines = in.nextInt();
        for (int i = 0; i < numLines; i++) {

            int numRows = in.nextInt();
            int numColumns = in.nextInt();
            in.nextLine();
            char[][] maze = new char[numRows][numColumns];
            for (int r = 0; r < numRows; r++) {
                maze[r] = in.nextLine().toCharArray();
            }
            int sR = 0;
            int sC = 0;
            for (int r = 0; r < numRows; r++) {
                for (int c = 0; c < numColumns; c++) {
                    if (maze[r][c] == 'S') {
                        sR = r;
                        sC = c;
                    }
                }
            }
            ArrayList<Node> list = new ArrayList<>();
            Node first = new Node(sR, sC);
            list.add(first);
            boolean found = false;
            while (!list.isEmpty()) {

                Node hold = list.remove(0);

                if (maze[hold.r][hold.c] == 'B') {
                    found = true;
                    break;
                }
                maze[hold.r][hold.c] = '#';
                if ((hold.r-1 >= 0) && maze[hold.r-1][hold.c] != '#') {
                    Node left = new Node(hold.r-1, hold.c);
                    //System.out.println("left");
                    list.add(left);
                }
                if ((hold.r+1 < numRows) && maze[hold.r+1][hold.c] != '#') {
                    Node right = new Node(hold.r+1, hold.c);
                    //System.out.println("right" + (hold.r + 1) + " " + hold.c);
                    list.add(right);
                }
                if ((hold.c-1 >= 0) && maze[hold.r][hold.c-1] != '#') {
                    Node up = new Node(hold.r, hold.c-1);
                    //System.out.println("up");
                    list.add(up);
                }
                if ((hold.c+1 < numColumns) && maze[hold.r][hold.c+1] != '#') {
                    Node down = new Node(hold.r, hold.c+1);
                    //System.out.println("down" + hold.r + " " + (hold.c + 1));
                    list.add(down);
                }
            }

            if (!found) {
                System.out.println("NOT POSSIBLE");
            } else {
                System.out.println("POSSIBLE");
            }

        }

    }

    private static class Node {

        int r;
        int c;

        private Node(int r, int c) {
            this.r = r;
            this.c = c;
        }

    }

}

Как я могу изменить это, чтобы это нетайм-аут?

...