Breadth-First Search takes way too long to solve maze

Question

I have an big, open maze like this:

############################################################
#.....................#...#................#.........#.....#
#..##.......x.........#.#.#...#.........x..#......#..#.....#
#...#.......#....#....#.#.#...#...####.....####...#..#####.#
#.....###...#....#....###.#...#.........#.........#......#.#
####.#..#...#....#........#...#####..#..#...#######..##..#.#
#....##.....#....#................#..####......#...........#
#......##...######........x....................#......######
#....##........................................#...........#
#.........##########...############........#...#...####....#
#.....#...#..#..#..#......#.......#........#...#....###....#
#######...#..#..#..#......#.......#.....####...............#
#.....#...#..#..#..#......#.......#........................#
#.....#####..#..#..#......#.......######............x......#
#.........................#................................#
#..................x......#..##..........#####.............#
#.........................####.............................#
#..........................................................#
#....##.....#....#................#..####......#...........#
#.....s##...######.............................#......######
#....##........................................#...........#
#.........##########...############........#...#...####....#
#.....#...#..#..#..#......#.......#........#...#....###....#
#######...#..#..#..#......#.......#...x.####...............#
#.....#...#..#...x.#......#.......#.................#......#
#.....#####..#..#..#...#..###....#######............######.#
#...............#..x...#..#.....##...........####...#......#
#...............#......#.........#.........##...#..........#
#...............#......#.........#..........#............#.#
############################################################

"s" is the starting point. And there are multiple destination points "x". I just need to find one destination. The BFS algorithm can find a solution pretty quick if a destination is close to the starting point. If they are further away like in the example above, it takes endless time. So my questions are: a) Is the algorithm bad for this specific type of maze and should I rather use A* or something like that. b) Is my implementation bad?

Implementation:

public class BFS {

    public static String getPath(String[][] map) {
        String[] ways = { "L", "R", "U", "D" }; // directions to go
        Queue<String> q = new LinkedList<>();
        q.offer("");
        String path = "";

        while (!foundBait(map, path)) {
            path = q.poll();

            for (String s : ways) {
                String newPath = path + s;
                if (valid(map, newPath))
                    q.offer(newPath);
            }
        }
        return path;
    }

    private static boolean foundBait(String[][] map, String moves) {
        int xStart = 0;
        int yStart = 0;

        for (int y = 0; y < map.length; y++)
            for (int x = 0; x < map[0].length; x++)
                if (map[y][x].equals("s")) {
                    xStart = x;
                    yStart = y;
                }

        int i = xStart;
        int j = yStart;

        for (int s = 0; s < moves.length(); s++) {

            if (moves.charAt(s) == "L".charAt(0))
                i--;
            else if (moves.charAt(s) == "R".charAt(0))
                i++;
            else if (moves.charAt(s) == "U".charAt(0))
                j--;
            else if (moves.charAt(s) == "D".charAt(0))
                j++;

        }

        if (map[j][i].equals("x"))
            return true;

        return false;
    }

    private static boolean valid(String[][] map, String moves) {
        int xStart = 0;
        int yStart = 0;

        for (int y = 0; y < map.length; y++)
            for (int x = 0; x < map[0].length; x++)
                if (map[y][x].equals("s")) {
                    xStart = x;
                    yStart = y;
                }

        int i = xStart;
        int j = yStart;

        for (int s = 0; s < moves.length(); s++) {

            if (moves.charAt(s) == "L".charAt(0))
                i--;
            else if (moves.charAt(s) == "R".charAt(0))
                i++;
            else if (moves.charAt(s) == "U".charAt(0))
                j--;
            else if (moves.charAt(s) == "D".charAt(0))
                j++;

            if (!(0 <= i && i < map[0].length && 0 <= j && j < map.length))
                return false;
            else if (map[j][i].equals("#") || map[j][i].equals("-"))
                return false;

        }
        return true;
    }

}

Answer 1

As stated in the comments, problem was not marking the nodes added to the paths, and the solution is to use a second matrix for marking.