fork(1) download
copy 
  1. import java.util.*;
  2. import static java.lang.Math.*;
  3.  
  4. class Point {
  5.     int r, c;
  6.     public Point(int r, int c) {
  7.         this.r = r;
  8.         this.c = c;
  9.     }
  10.     @Override public String toString() {
  11.         return r + ":" + c;
  12.     }
  13.     @Override public boolean equals(Object obj) {
  14.         if(!(obj instanceof Point)) { return false; }
  15.         Point that = (Point)obj;
  16.         return this.r == that.r && this.c == that.c;
  17.     }
  18.     @Override public int hashCode() {
  19.         return r * 17 + c * 31;
  20.     }
  21. }
  22.  
  23. public class RecursiveMeiro {
  24.     private String[] f(String[][] field) {
  25.         int R = field.length;
  26.         String[] res = new String[R];
  27.         for(int r=0; r<R; r++) {
  28.             res[r] = field[r][0];
  29.         }
  30.         return res;
  31.     }
  32.  
  33.     int[] dr = {  0, 0, 1, -1 };
  34.     int[] dc = { -1, 1, 0,  0 };
  35.     String[] direction = { "l", "r", "d", "u" };
  36.  
  37.     private String h(List<Point> list) {
  38.         String res = "";
  39.         for(int i=list.size()-1; i>=1; i--) {
  40.             Point cur  = list.get(i);
  41.             Point prev = list.get(i-1);
  42.             if(cur.r == prev.r) {
  43.                 if(cur.c < prev.c) { res += "r"; }
  44.                 else               { res += "l"; }
  45.             } else {
  46.                 if(cur.r < prev.r) { res += "d"; }
  47.                 else               { res += "u"; }
  48.             }
  49.         }
  50.         return res;
  51.     }
  52.  
  53.  
  54.     private String g(char[][] css, Point start, Point goal, int R, int C) {
  55.         Set<Point> vis = new HashSet<Point>();
  56.         Map<Point, Point> prev  = new HashMap<Point, Point>();
  57.         Queue<Point> q = new LinkedList<Point>();
  58.         Point cur = start;
  59.         q.add(cur);
  60.         vis.add(cur);
  61.         while(!q.isEmpty()) {
  62.             cur = q.remove();
  63.             if(cur.equals(goal)) { break; }
  64.             else {
  65.                 int r = cur.r;
  66.                 int c = cur.c;
  67.                 for(int i=0; i<4; i++) {
  68.                     int nr = r + dr[i];
  69.                     int nc = c + dc[i];
  70.                     if(nr < 0 || R <= nr || nc < 0 || C <= nc) { continue; }
  71.                     if(css[nr][nc] == '#') { continue; }
  72.                     Point node = new Point(nr, nc);
  73.                     if(vis.contains(node)) { continue; }
  74.                     q.add(node);
  75.                     vis.add(node);
  76.                     prev.put(node, cur);
  77.                 }
  78.             }
  79.         }
  80.         List<Point> directions = new LinkedList<Point>();
  81.         for(Point node = goal; node != null; node = prev.get(node)) {
  82.             directions.add(node);
  83.         }
  84.         return h(directions);
  85.     }
  86.  
  87.     public String adventure(String[][] field) {
  88.         String[] f = f(field);
  89.         int R = f.length;
  90.         char[][] css = new char[R][];
  91.         for(int r=0; r<R; r++) {
  92.             css[r] = f[r].toCharArray();
  93.         }
  94.         int C = css[0].length;
  95.         Point start = null, goal = null;
  96.         for(int r=0; r<R; r++) {
  97.             for(int c=0; c<C; c++) {
  98.                 if(css[r][c] == 'S') { start = new Point(r, c); }
  99.                 if(css[r][c] == 'G') { goal  = new Point(r, c); }
  100.             }
  101.         }
  102.         return g(css, start, goal, R, C);
  103.     }
  104.  
  105.     private void doIt() {
  106.         String[][] sss1 = {
  107.             { "#####" },
  108.             { "#S..#" },
  109.             { "###.#" },
  110.             { "#G..#" },
  111.             { "#####" },
  112.         };
  113.         String res1 = adventure(sss1);
  114.         System.out.println(res1);
  115.  
  116.         String[][] sss2 = {
  117.             { "#####" },
  118.             { "#..G#" },
  119.             { "#...#" },
  120.             { "#...#" },
  121.             { "#...#" },
  122.             { "#S..#" },
  123.             { "#####" },
  124.         };
  125.         String res2 = adventure(sss2);
  126.         System.out.println(res2);
  127.  
  128.         String[][] sss3 = {
  129.             { "####" },
  130.             { "#S.#" },
  131.             { "#.G#" },
  132.             { "####" },
  133.         };
  134.         String res3 = adventure(sss3);
  135.         System.out.println(res3);
  136.  
  137.         String[][] sss4 = {
  138.             { "#######" },
  139.             { "#.....#" },
  140.             { "#.#.#.#" },
  141.             { "#.#S#.#" },
  142.             { "#.###.#" },
  143.             { "#.#G#.#" },
  144.             { "#.#.#.#" },
  145.             { "#.....#" },
  146.             { "#######" },
  147.         };
  148.         String res4 = adventure(sss4);
  149.         System.out.println(res4);
  150.  
  151.         String[][] sss5 = {
  152.             { "#######" },
  153.             { "#.....#" },
  154.             { "#.....#" },
  155.             { "#..S..#" },
  156.             { "#.....#" },
  157.             { "#..G..#" },
  158.             { "#.....#" },
  159.             { "#.....#" },
  160.             { "#######" },
  161.         };
  162.         String res5 = adventure(sss5);
  163.         System.out.println(res5);
  164.  
  165.         String[][] sss6 = {
  166.             { "#######" },
  167.             { "#.....#" },
  168.             { "#.....#" },
  169.             { "#.....#" },
  170.             { "#.G...#" },
  171.             { "#.....#" },
  172.             { "#...S.#" },
  173.             { "#.....#" },
  174.             { "#######" },
  175.         };
  176.         String res6 = adventure(sss6);
  177.         System.out.println(res6);
  178.     }
  179.  
  180.     public static void main(String[] args) {
  181.         new RecursiveMeiro().doIt();
  182.     }
  183. }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rd6HC
language:
Java (HotSpot 12)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!