Path Finder #1: can you reach the exit?

kata programming

مساله:

شما در نقطه [0,0] یک ماتریس NxN هستید و فقط می توانید در چهار جهت اصلی حرکت کنید.(یعنی شمال، جنوب، شرق و غرب)

اگر توانستید به نقطه [N-1, N-1] برسید عبارت true را برگردانید، در غیر اینصورت false را برگردانید.

  • خانه خالی با . نشان داده می شود
  • دیوارها با W نمایش داده می شود
  • در تمام موارد ورود و خروج خالی هستند

Description:

Task

You are at position [0, 0] in maze NxN and you can only move in one of the four cardinal directions (i.e. North, East, South, West). Return true if you can reach position [N-1, N-1] or false otherwise.

Empty positions are marked ..

Walls are marked W.

Start and exit positions are empty in all test cases.


راه حل ها:

public class Finder {
  
  private static class Pos {
    final int x, y;
    Pos(int x, int y) { this.x = x; this.y = y; } 
    Pos[] neighbours() { return new Pos[]{ new Pos(x-1,y), new Pos(x+1,y), new Pos(x,y-1), new Pos(x,y+1) }; }
    boolean onPath(char[][]g) { return x >= 0 && x < g[0].length && y >= 0 && y < g.length && g[y][x] == '.'; }    
  }

  static boolean pathFinder(String maze) {
    final String rows[] = maze.split("\n");
    final char[][] grid = new char[rows.length][];
    for (int i = 0; i < rows.length; i++) grid[i] = rows[i].toCharArray();
    return findExit(new Pos(0,0), grid);
  }
  
  private static boolean findExit(Pos p, char[][]g) {        
    if (p.x == g.length-1 && p.x == p.y) return true; // We made it to the exit!    
    if (!p.onPath(g)) return false;
    g[p.y][p.x] = 'B';  // drop a breadcrumb
    final Pos[] n = p.neighbours();
    return findExit(n[0],g) | findExit(n[1],g) | findExit(n[2],g) | findExit(n[3],g);
  }

}
public class Finder {
    private static boolean[][] graph;

    public static boolean pathFinder(String maze) {
        initGraph(maze);
        goTo(0, 0);
        return graph[graph.length - 1][graph.length - 1];
    }

    private static void initGraph(String maze){
        String[] lines = maze.split("\n");
        graph = new boolean[lines.length][lines.length];
        for(int i=0; i<lines.length; i++)
            for(int j=0; j<lines.length; j++)
                graph[i][j] = (lines[i].charAt(j)=='W')?true:false;
    }

    private static void goTo(int i, int j){
        if(i==-1 || i==graph.length || j==-1 || j==graph.length || graph[i][j])
            return;
        graph[i][j] = true;
        goTo(i, j-1);
        goTo(i, j+1);
        goTo(i+1, j);
        goTo(i-1, j);
    }
}
import java.util.LinkedList;

public class Finder {
    
    public static boolean pathFinder(String maze) {
        char[] mazeArray = maze.toCharArray();
        int n = ((int) Math.sqrt(4 * maze.length() + 5) - 1) / 2;
        LinkedList<Integer> toTest = new LinkedList<>();
        toTest.add(0);
        while (!toTest.isEmpty()) {
            int p = toTest.pollFirst();
            if (p == mazeArray.length-1) return true;
            if (mazeArray[p]!='.') continue;
            mazeArray[p]='*';
            int y = p / (n + 1);
            int x = p - y * (n + 1);
            if (y>0 && mazeArray[p-n-1]=='.') toTest.push(p-n-1);
            if (y<n-1 && mazeArray[p+n+1]=='.') toTest.push(p+n+1);
            if (x>0 && mazeArray[p-1]=='.') toTest.push(p-1);
            if (x<n-1 && mazeArray[p+1]=='.') toTest.push(p+1);
        }
        return false;
    }
}
import java.util.*;
import java.util.stream.*;
import java.awt.Point;


public class Finder {
    
    final private static List<Point> MOVES = Arrays.asList(new Point(1,0), new Point(0,1), new Point(0,-1), new Point(-1,0));
    
    
    static boolean pathFinder(String maze) {
        
        int S = (int) Math.sqrt(maze.length()) - 1;
        if (S == 0) return true;
            
        final Set<Point> bag  = new HashSet<>();
        int x = -1;
        for (String line: maze.split("\n")) { x++;
            for (int y=0 ; y < line.length() ; y++) 
                if (line.charAt(y)=='.') bag.add(new Point(x,y));
        }
        bag.remove(new Point(0,0));
        
        final Point     end    = new Point(S,S);
        final boolean[] hasEnd = {false};
        Set<Point>      look   = new HashSet<>(Arrays.asList(new Point(0,0)));
        
        while (!look.isEmpty()) {
            if (hasEnd[0]) return true;
            look = look.stream()
                       .flatMap( p -> MOVES.stream().map( d -> new Point(p.x+d.x, p.y+d.y) ))
                       .distinct()
                       .filter(  p -> { if (p.equals(end)) hasEnd[0] = true;
                                        if (bag.contains(p)) {
                                            bag.remove(p);
                                            return true;
                                        } else return false; })
                      .collect(Collectors.toSet());
        }
        return false;
    }
}
class Finder {
    static int n;
    static int m;
    static String[] maze;
    static boolean[][] visited;

    static boolean pathFinder(String imaze) {
        String[] tmaze = imaze.split("\n");

        n = tmaze.length;
        m = tmaze[0].length();
        maze = tmaze;
        visited = new boolean[n][m];

        return dfs(0, 0);
    }

    static boolean dfs(int i, int j){
        if(i < 0 || n <= i || j < 0 || m <= j || maze[i].charAt(j) == 'W' || visited[i][j])
            return false;

        if(i == n-1 && j == m-1)
            return true;

        visited[i][j] = true;

        return dfs(i-1, j) ||
               dfs(i+1, j) ||
               dfs(i, j-1) ||
               dfs(i, j+1);
    }
}
public class Finder {
    
  static boolean pathFinder(String maze) {
        String[] arrBld = maze.split("\n");
        int[][] arr = new int[arrBld.length][arrBld.length];
        for (int i = 0; i < arrBld.length; i++){
          for (int j = 0; j < arrBld.length; j++){
          if (arrBld[i].charAt(j) == '.') arr[i][j] = 0;
          else arr[i][j] = 1;
          }
        }
        return goPath(arr, new int[]{0, 0}, 1, new int[]{arr.length - 1, arr[0].length - 1});
    }

  public static boolean goPath(int[][] map, int[] pos, int counter, int[] aim) {
    try {
      if (pos[0] == aim[0] && pos[1] == aim[1])
        return true;
      else if (map[pos[0]][pos[1]] == 0) {
        map[pos[0]][pos[1]] = 1;
        if (goPath(map, new int[] { pos[0] + 1, pos[1] }, counter + 1, aim) ||
            goPath(map, new int[] { pos[0] - 1, pos[1] }, counter + 1, aim) ||
            goPath(map, new int[] { pos[0], pos[1] + 1 }, counter + 1, aim) ||
            goPath(map, new int[] { pos[0], pos[1] - 1 }, counter + 1, aim)) return true;
      }
    } catch (Exception e) {}
    return false;
  }
}
import java.util.*;

public class Finder {
    static boolean pathFinder(String maze) {
      var grid = Arrays.stream(maze.split("\n")).map(row -> row.toCharArray()).toArray(char[][]::new);
      dfs(grid, 0, 0);
      return grid[grid.length - 1][grid[0].length - 1] == 'x';
    }
    private static void dfs(char[][] maze, int x, int y) {
      if (x < 0 || y < 0 || x >= maze.length || y >= maze[0].length || maze[x][y] != '.')
        return;
      maze[x][y] = 'x';
      dfs(maze, x + 1, y);
      dfs(maze, x - 1, y);
      dfs(maze, x, y + 1);
      dfs(maze, x, y - 1);
    }
}
import java.util.*;
public class Finder {
    
    static boolean pathFinder(String maze) {
        String[] spl = maze.split("\n");
        char[][] grid = new char[spl.length][];
        Node[][] nodes = new Node[spl.length][];
        for(int i = 0; i < spl.length; i++){
          grid[i] = spl[i].toCharArray();
          nodes[i] = new Node[grid[i].length];
          for(int j = 0; j < grid[i].length; j++){
            nodes[i][j] = new Node(grid[i][j], i, j);
          }
        }
        Deque<Node> stack = new ArrayDeque<Node>(); 
        stack.push(nodes[0][0]);
        int x=0, y=0;
        while(!stack.isEmpty()){
          Node curr = stack.pop();
          curr.visited = true;
          x = curr.x;
          y = curr.y;
          if(x==nodes.length-1 && y == nodes.length-1){
            return true;
          }
          if(x+1 < nodes.length && !nodes[x+1][y].visited && nodes[x+1][y].ch =='.'){
            stack.push(nodes[x+1][y]);
          }
          if(x-1 >= 0 && !nodes[x-1][y].visited && nodes[x-1][y].ch =='.'){
            stack.push(nodes[x-1][y]);
          }
          if(y+1 < nodes.length && !nodes[x][y+1].visited && nodes[x][y+1].ch =='.'){
            stack.push(nodes[x][y+1]);
          }
          if(y-1 >= 0 &&!nodes[x][y-1].visited && nodes[x][y-1].ch =='.'){
            stack.push(nodes[x][y-1]);
          }
        }
        return false;
    }
}

class Node{
  public boolean visited;
  char ch;
  int x, y;
  
  public Node(char ch, int x, int y){
    this.ch = ch;
    visited = false;
    this.x = x;
    this.y = y;
  }
  
  
}

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد.