fork download
copy 
  1. import java.util.*;
  2. import static java.lang.Math.*;
  3.  
  4. class Point {
  5.     int r, c, d;
  6.     public Point(int r, int c) {
  7.         this.r = r;
  8.         this.c = c;
  9.     }
  10.     public Point(int r, int c, int d) {
  11.         this(r, c);
  12.         this.d = d;
  13.     }
  14. }
  15.  
  16. public class RecursiveMeiro {
  17.     private String[] f(String[][] field) {
  18.         int R = field.length;
  19.         String[] res = new String[R];
  20.         for(int r=0; r<R; r++) {
  21.             res[r] = field[r][0];
  22.         }
  23.         return res;
  24.     }
  25.  
  26.     int[] dr = {  0, 0, 1, -1 };
  27.     int[] dc = { -1, 1, 0,  0 };
  28.  
  29.     private String bfs(char[][] css) {
  30.         int R = css.length;
  31.         int C = css[0].length;
  32.         Queue<Point> q = new LinkedList<Point>();
  33.         int[][] iss = new int[R][C];
  34.         for(int r=0; r<R; r++) {
  35.             for(int c=0; c<C; c++) {
  36.                 if(css[r][c] == '#') {
  37.                     iss[r][c] = 987654321;
  38.                 }
  39.             }
  40.         }
  41.         int sr = -1, sc = -1;
  42. here:   for(int r=0; r<R; r++) {
  43.             for(int c=0; c<C; c++) {
  44.                 if(css[r][c] == 'S') {
  45.                     q.add(new Point(r, c, 0));
  46.                     iss[r][c] = 0;
  47.                     css[r][c] = '#';
  48.                     sr = r;
  49.                     sc = c;
  50.                     break here;
  51.                 }
  52.             }
  53.         }
  54.         String res = "";
  55.         int goal = -1;
  56.         while(!q.isEmpty()) {
  57.             Point p = q.remove();
  58.             int r = p.r, c = p.c;
  59.             for(int i=0; i<4; i++) {
  60.                 int nr = r + dr[i];
  61.                 int nc = c + dc[i];
  62.                 if(nr < 0 || R <= nr || nc < 0 || C <= nc) { continue; }
  63.                 if(css[nr][nc] == '#') { continue; }
  64.                 css[nr][nc] = '#';
  65.                 q.add(new Point(nr, nc, p.d+1));
  66.                 iss[nr][nc] = p.d+1;
  67.                 goal = max(goal, p.d+1);
  68.                 if(css[nr][nc] == 'G') { break; }
  69.             }
  70.         }
  71.         int cur = 0;
  72.         int r = sr;
  73.         int c = sc;
  74.         for( ; cur < goal ; ) {
  75.             if(iss[r][c] == cur) {
  76.                 for(int i=0; i<4; i++) {
  77.                     int nr = r + dr[i];
  78.                     int nc = c + dc[i];
  79.                     if(nr < 0 || R <= nr || nc < 0 || C <= nc) { continue; }
  80.                     if(iss[nr][nc] == cur+1) {
  81.                         if(i == 0) { res += "l"; }
  82.                         else if(i == 1) { res += "r"; }
  83.                         else if(i == 2) { res += "d"; }
  84.                         else if(i == 3) { res += "u"; }
  85.                         cur += 1;
  86.                         r = nr;
  87.                         c = nc;
  88.                     }
  89.                 }
  90.             }
  91.         }
  92.         return res;
  93.     }
  94.  
  95.     public String adventure(String[][] field) {
  96.         String[] f = f(field);
  97.         int R = f.length;
  98.         char[][] css = new char[R][];
  99.         for(int r=0; r<R; r++) {
  100.             css[r] = f[r].toCharArray();
  101.         }
  102.         return bfs(css);
  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.  
  152.     public static void main(String[] args) {
  153.         new RecursiveMeiro().doIt();
  154.     }
  155. }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/vXge0
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!