fork download
copy 
  1. /*
  2. MIT License
  3.  
  4. Copyright (c) 2019 Shusuke Kusao
  5.  
  6. Permission is hereby granted, free of charge, to any person obtaining a copy
  7. of this software and associated documentation files (the "Software"), to deal
  8. in the Software without restriction, including without limitation the rights
  9. to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  10. copies of the Software, and to permit persons to whom the Software is
  11. furnished to do so, subject to the following conditions:
  12.  
  13. The above copyright notice and this permission notice shall be included in all
  14. copies or substantial portions of the Software.
  15.  
  16. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17. IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18. FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  19. AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  20. LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  21. OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  22. SOFTWARE.
  23. */
  24. // run on java 1.8
  25.  
  26. import java.io.*;
  27. import java.util.*;
  28. import java.util.function.BiConsumer;
  29.  
  30. class Ideone {
  31.  
  32.     public static final int MAX_SIMPLICITY = 100;
  33.     public static final char WALL = '#';
  34.     public static final char ROAD = '.';
  35.     public static final char START = 'S';
  36.     public static final char GOAL = 'G';
  37.     public static final BiConsumer<int[], ArrayDeque<int[]>> ADD_BFS = (point, deq) -> deq.addFirst(point);
  38.     public static final BiConsumer<int[], ArrayDeque<int[]>> ADD_DFS = (point, deq) -> deq.addLast(point);
  39.  
  40.     private static final char TEMP_STOPPER = '!';
  41.     private static final int INF = Integer.MAX_VALUE;
  42.  
  43.     public static void main(String args[]) {
  44.         // 標準入力例
  45.         // 迷路作る
  46.         // 11 13 0 0 -make -debug
  47.         // 作って解く
  48.         // 5 15 0 0 -bfs -debug
  49.         // 一本道マシマシ
  50.         // 5 15 100 0 -bfs -debug
  51.         // 回廊がないじゃん->適当に壁を掘る
  52.         // 5 21 0 20 -bfs -debug
  53.         // 最短経路でなく到達可能か調べるやつ
  54.         // 5 21 0 20 -dfs -debug
  55.  
  56.         // 上限調査用
  57.         // 2501 2501 50 1000 -make -no-debug
  58.         // 2501 2501 50 1000 -bfs -no-debug
  59.         // 2501 2501 50 1000 -dfs -no-debug
  60.  
  61.         Scanner scn = new Scanner(System.in);
  62.         PrintWriter cout = new PrintWriter(System.out);
  63.  
  64.         int height = scn.nextInt();
  65.         int width = scn.nextInt();
  66.         int simplicity = scn.nextInt();
  67.         int circuits = scn.nextInt();
  68.         String proc = scn.next();
  69.         boolean debug = Objects.equals("-debug", scn.next());
  70.  
  71.         BiConsumer<int[], ArrayDeque<int[]>> addDeq = null;
  72.         if (Objects.equals(proc, "-bfs")) {
  73.             addDeq = ADD_BFS;
  74.         } else if (Objects.equals(proc, "-dfs")) {
  75.             addDeq = ADD_DFS;
  76.         } else {
  77.             // makeのみ。
  78.         }
  79.  
  80.         // make:迷路を作ります
  81.         char[][] maze = make(height, width, simplicity, circuits);
  82.         if (debug) {
  83.             cout.println("make:");
  84.             for (char[] line : maze)
  85.                 cout.println(String.valueOf(line));
  86.         }
  87.  
  88.         if (addDeq == null) {
  89.             // makeのみ。
  90.         } else {
  91.  
  92.             // bfs/dfs:迷路を解きます
  93.             xfs(maze, addDeq);
  94.             if (debug) {
  95.                 cout.println(proc + ":");
  96.                 for (char[] line : maze)
  97.                     cout.println(String.valueOf(line));
  98.             }
  99.  
  100.         }
  101.  
  102.         cout.flush();
  103.     }
  104.  
  105.     public static char[][] make(int height, int width, int simplicity, int circuits) {
  106.         final int h = height; // 縦幅
  107.         final int w = width; // 横幅
  108.  
  109.         if (3 > h || h % 2 == 0) {
  110.             System.out.println("3 <= height の奇数のみ入力可能です");
  111.             return new char[0][0];
  112.         }
  113.         if (3 > w || w % 2 == 0) {
  114.             System.out.println("3 <= width の奇数のみ入力可能です");
  115.             return new char[0][0];
  116.         }
  117.         if (h * w == 9) {
  118.             System.out.println("開始地点と終了地点を置けません（周囲１マスは外周で、壁になります）");
  119.             return new char[0][0];
  120.         }
  121.         if (0 > simplicity || simplicity > MAX_SIMPLICITY) {
  122.             System.out.println("0 <= simplicity <= " + MAX_SIMPLICITY + " のみ入力可能です");
  123.             return new char[0][0];
  124.         }
  125.         if (0 > circuits) {
  126.             System.out.println("0 <= circuits のみ入力可能です");
  127.             return new char[0][0];
  128.         }
  129.  
  130.         // 戻り値（迷路）
  131.         char[][] maze = new char[h][w];
  132.  
  133.         // （１）壁で埋め尽くします
  134.         for (char[] line : maze)
  135.             Arrays.fill(line, WALL);
  136.         // 外周は一時的に専用文字に書き換えます（番兵法）
  137.         Arrays.fill(maze[0], TEMP_STOPPER);
  138.         Arrays.fill(maze[h - 1], TEMP_STOPPER);
  139.         for (int i = 0; i < h; i++) {
  140.             maze[i][0] = TEMP_STOPPER;
  141.             maze[i][w - 1] = TEMP_STOPPER;
  142.         }
  143.  
  144.         // 上下左右
  145.         int[] dy = { 0, -1, 0, 1 };
  146.         int[] dx = { -1, 0, 1, 0 };
  147.         int dn = dx.length;
  148.  
  149.         // 乱数
  150.         Random rand = new Random(new Date().getTime());
  151.  
  152.         // 到達済み地点リスト
  153.         PriorityQueue<int[]> q = new PriorityQueue<>((arr1, arr2) -> Integer.compare(arr1[2], arr2[2]));
  154.  
  155.         // （２）真ん中辺りの奇数マスに道を開けます
  156.         int[] stt = { h / 4 * 2 + 1, w / 4 * 2 + 1, 0 };
  157.         maze[stt[0]][stt[1]] = ROAD;
  158.  
  159.         // （３）真ん中を到達済地点リストに追加します
  160.         q.add(stt);
  161.         while (q.isEmpty() == false) {
  162.  
  163.             // （４）到達済地点リストの先頭を取り出します
  164.             int[] p = q.poll();
  165.             int y = p[0];
  166.             int x = p[1];
  167.  
  168.             // （５）上下左右から適当に選んで掘ります
  169.             int drand = rand.nextInt(dn);
  170.             for (int d = 0; d < dn; d++) {
  171.                 int dir = (drand + d) % dn;
  172.                 // 隣のマス
  173.                 int ny1 = y + dy[dir];
  174.                 int nx1 = x + dx[dir];
  175.                 if (maze[ny1][nx1] == TEMP_STOPPER)
  176.                     // 外周なので掘れません
  177.                     continue;
  178.                 // 隣の隣のマス
  179.                 int ny2 = ny1 + dy[dir];
  180.                 int nx2 = nx1 + dx[dir];
  181.                 if (maze[ny2][nx2] == ROAD)
  182.                     // 別の経路で既に掘ってます
  183.                     continue;
  184.  
  185.                 // （６）よし掘れる、掘ろう
  186.                 maze[ny1][nx1] = ROAD;
  187.                 maze[ny2][nx2] = ROAD;
  188.  
  189.                 // （７）simplicityパーセントで続きを掘ります
  190.                 // (100 - simplicity)パーセントでランダム順に掘る予約をします
  191.                 int priority;
  192.                 if (simplicity == 0) {
  193.                     priority = rand.nextInt(INF);
  194.                 } else if (simplicity == MAX_SIMPLICITY) {
  195.                     priority = -1;
  196.                 } else if (rand.nextInt(MAX_SIMPLICITY) < simplicity) {
  197.                     priority = -1;
  198.                 } else {
  199.                     priority = rand.nextInt(INF);
  200.                 }
  201.  
  202.                 // （７）掘った先を到達済地点リストに追加します
  203.                 q.add(new int[] { ny2, nx2, priority });
  204.  
  205.                 // 現在地点もリストに戻します
  206.                 // （１方向に掘ったら他の方向を掘らずに終わるので、戻しておかないと掘り漏れが発生します。全方向を掘り終わっていたら単に空振りします）
  207.                 q.add(new int[] { p[0], p[1], rand.nextInt(INF) });
  208.                 // 他の方向は掘らずに終わります
  209.                 break;
  210.             }
  211.         }
  212.         // （８）到達済地点リストが空になったら掘り終わりです
  213.  
  214.         // （９）仕上げ１：外周をただの壁に戻します
  215.         Arrays.fill(maze[0], WALL);
  216.         Arrays.fill(maze[h - 1], WALL);
  217.         for (int i = 0; i < h; i++) {
  218.             maze[i][0] = WALL;
  219.             maze[i][w - 1] = WALL;
  220.         }
  221.  
  222.         // 壁、道カウント
  223.         int roadsCount = 0;
  224.         int wallsCount = 0;
  225.         for (int j = h - 2; j >= 1; j--) {
  226.             char[] line = maze[j];
  227.             for (int i = line.length - 2; i >= 1; i--) {
  228.                 if (line[i] == TEMP_STOPPER)
  229.                     line[i] = WALL;
  230.                 if (line[i] == ROAD)
  231.                     roadsCount += 1;
  232.                 if (line[i] == WALL)
  233.                     wallsCount += 1;
  234.             }
  235.         }
  236.  
  237.         // （１０）仕上げ２：適当な道に開始地点と終了地点を置きます
  238.         int startPoint = rand.nextInt(roadsCount);
  239.         int endPoint = rand.nextInt(roadsCount);
  240.         while (startPoint == endPoint)
  241.             endPoint = rand.nextInt(roadsCount);
  242.         int road = 0;
  243.         for (int j = h - 2; j >= 1; j--) {
  244.             char[] line = maze[j];
  245.             for (int i = line.length - 2; i >= 1; i--) {
  246.                 if (line[i] != ROAD)
  247.                     continue;
  248.                 if (road == startPoint)
  249.                     line[i] = START;
  250.                 if (road == endPoint)
  251.                     line[i] = GOAL;
  252.                 road += 1;
  253.             }
  254.         }
  255.  
  256.         // （１１）仕上げ３：circuitsの指定だけ、適当に壁を掘ります
  257.         // 作成直後の迷路はグラフ理論で言う木です。閉路＝回り道がありません。
  258.         // そのままだと退屈なので適当に回り道を作ります
  259.         // 重複ありです。入力とリアルラック次第では同じ位置を２回掘ろうとします
  260.         Set<Integer> c = new HashSet<>(circuits);
  261.         for (int i = 0; i < circuits; i++)
  262.             c.add(rand.nextInt(wallsCount));
  263.         int wall = 0;
  264.         for (int j = h - 2; j >= 1; j--) {
  265.             char[] line = maze[j];
  266.             for (int i = line.length - 2; i >= 1; i--) {
  267.                 if (line[i] != WALL)
  268.                     continue;
  269.                 if (c.contains(wall))
  270.                     line[i] = ROAD;
  271.                 wall += 1;
  272.             }
  273.         }
  274.  
  275.         // ありがとうございました
  276.         return maze;
  277.     }
  278.  
  279.     public static void xfs(char[][] maze, BiConsumer<int[], ArrayDeque<int[]>> addDeq) {
  280.         // 最短経路を探してmazeを書き換えます（破壊的動作）
  281.  
  282.         final int h = maze.length; // 縦幅
  283.         final int w = maze[0].length; // 横幅
  284.  
  285.         // 上下左右
  286.         int[] dy = { 0, -1, 0, 1 };
  287.         int[] dx = { -1, 0, 1, 0 };
  288.         int dn = dx.length;
  289.  
  290.         // 最短距離メモvis[i][j] = 開始地点からmaze[i][j]に到達するまでの最短距離
  291.         int[][] vis = new int[h][w];
  292.         for (int[] v : vis)
  293.             Arrays.fill(v, -1); // 全部、未計算
  294.  
  295.         int[] s = null;
  296.         int[] g = null;
  297.         for (int i = 0; i < h; i++) {
  298.             for (int j = 0; j < w; j++) {
  299.                 switch (maze[i][j]) {
  300.                 case START:
  301.                     // （１）開始地点を検出します、３つ目の数は開始地点からの最短距離です
  302.                     s = new int[] { i, j, 0 };
  303.                     break;
  304.                 case GOAL:
  305.                     // （２）終了地点も検出します、ついでに一時的に道扱いします
  306.                     maze[i][j] = ROAD;
  307.                     g = new int[] { i, j };
  308.                     break;
  309.                 case WALL:
  310.                     // （３）壁マスは到達不可能（超長距離）としておきます
  311.                     vis[i][j] = INF;
  312.                     break;
  313.                 default:
  314.                 }
  315.             }
  316.         }
  317.         if (s == null || g == null) {
  318.             throw new IllegalArgumentException("開始地点" + START + "または終了地点" + GOAL + "がありません");
  319.         }
  320.  
  321.         // （２）開始地点をコレクション（キューまたはスタック）に入れます
  322.         ArrayDeque<int[]> deq = new ArrayDeque<>();
  323.         deq.add(s);
  324.         vis[s[0]][s[1]] = 0;
  325.  
  326.         while (deq.isEmpty() == false) {
  327.  
  328.             // （３）コレクションから取り出します
  329.             int[] p = deq.pollLast();
  330.             int y = p[0];
  331.             int x = p[1];
  332.             int m = p[2];
  333.             vis[y][x] = m;
  334.             if (y == g[0] && x == g[1]) {
  335.                 // （４）ゴールしてたら終了。
  336.                 break;
  337.             }
  338.  
  339.             // （５）上下左右に移動してみます
  340.             for (int d = 0; d < dn; d++) {
  341.                 // 隣のマスが
  342.                 int ny = y + dy[d];
  343.                 int nx = x + dx[d];
  344.                 if (vis[ny][nx] != -1)
  345.                     // 未計算でなければ別の隣のマスを探します
  346.                     continue;
  347.                 // 未計算の場合＝行ったことない道かゴールの場合
  348.                 int[] np = new int[] { ny, nx, 1 + m };
  349.                 // （６）分身の術！
  350.                 // コレクションに分身を入れておきます
  351.                 // 前述の取り出しがpollLastであることに注意。
  352.                 // BFSは取り出し時と逆に入れます（FIFO：先入先出法）
  353.                 // DFSは取り出し時と同じに入れます（LIFO：先入先出法）
  354.                 addDeq.accept(np, deq);
  355.             }
  356.         }
  357.         deq.clear();
  358.         if (vis[g[0]][g[1]] == -1) {
  359.             throw new IllegalArgumentException("終了地点に到達できませんでした");
  360.         }
  361.  
  362.         // 最短距離をmazeに書き込みましょう
  363.  
  364.         // （７）終了地点から初めて、開始地点に戻るまで
  365.         int[] p = Arrays.copyOf(g, g.length);
  366.         while (p[0] != s[0] || p[1] != s[1]) {
  367.             int y = p[0];
  368.             int x = p[1];
  369.             for (int d = 0; d < dn; d++) {
  370.                 int ny = y + dy[d];
  371.                 int nx = x + dx[d];
  372.                 if (vis[ny][nx] + 1 != vis[y][x])
  373.                     continue;
  374.                 // （８）最短距離の1桁目、0~9を書きこんで
  375.                 maze[y][x] = (char) (vis[y][x] % 10 + '0');
  376.                 // （９）一歩戻ります
  377.                 p[0] = ny;
  378.                 p[1] = nx;
  379.                 break;
  380.             }
  381.         }
  382.  
  383.         // 終了地点をマークに戻して
  384.         maze[g[0]][g[1]] = GOAL;
  385.         // 〜終わり〜
  386.     }
  387.  
  388. }
  389.  
Success #stdin #stdout 0.16s 2184192KB
comments (?)
stdin
copy 
23 51 50 10 -dfs -debug
stdout
copy 
make:
###################################################
#.........#.................#.........#.........#.#
#.###.#####..##.#.#.###.###.#.#####.#######.#####.#
#.#.......#.#.....#.....#...#.#.....#.............#
#.#.#.###.#######.###..####.#####.#####.#######.###
#.#.#.#.....#.#.......#...#.#.........#...#...#...#
#.###.#####.#.#..####.###.#.#####.###########G###.#
#...#...#.....#.#.#.#.#.#.#.#.#.........#.....#.#.#
#.###.#.###.#####.#.#.#.#.#.#.#####.#.###.###.#.#.#
#.....#...#..........S..#.......#...#...#.#.#...#.#
#.###.#######.###.#####.#.#.#.###.#########.###.#.#
#.#.....#.......#...#...#.#...#...#...........#...#
#.#.#.#####.#.###.#.#####.#.###.#.###..########.###
#.#.#.#.#.#.#...#.#...#...#.....#...#.#.#.........#
#####.#.#.###.#.###.###########.#####.#.#####.###.#
#.#.......#...#...#...#.........#...#.#.#.#.....#.#
#.#.#.#.###.###.#.#######.#.#######.#.#.#.#.#####.#
#...#.....#.#...#...#...#.#...........#.#.......#.#
###.###.###.#.#.#####.#########.#.#####.#.#####.###
#.#.#.....#.#.#.#.............#.#.#...........#...#
#.###.###.###.#.#.#####.#.#####.###.#.#####.###.#.#
#.......#...#.#.#...#...#...........#.....#.#...#.#
###################################################
-dfs:
###################################################
#.........#............01234#.........#.........#.#
#.###.#####..##.#.#.###9###5#.#####.#######.#####.#
#.#.......#.#.....#...78#..6#.#.....#.............#
#.#.#.###.#######.###56####7#####.#####.#######.###
#.#.#.#.....#.#......4#...#8#.........#...#...#...#
#.###.#####.#.#..####3###.#9#####.###########G###.#
#...#...#.....#.#.#.#2#.#.#0#.#.........#....8#.#.#
#.###.#.###.#####.#.#1#.#.#1#.#####.#.###.###7#.#.#
#.....#...#..........S..#..2....#...#...#.#.#654#.#
#.###.#######.###.#####.#.#3#.###.#########.###3#.#
#.#.....#.......#...#...#.#4..#...#...........#2..#
#.#.#.#####.#.###.#.#####.#5###.#.###..########1###
#.#.#.#.#.#.#...#.#...#...#67890#...#.#.#....890..#
#####.#.#.###.#.###.###########1#####.#.#####7###.#
#.#.......#...#...#...#....65432#...#.#.#.#456..#.#
#.#.#.#.###.###.#.#######.#7#######.#.#.#.#3#####.#
#...#.....#.#...#...#...#.#89012......#.#012....#.#
###.###.###.#.#.#####.#########3#.#####.#9#####.###
#.#.#.....#.#.#.#.............#4#.#2345678....#...#
#.###.###.###.#.#.#####.#.#####5###1#.#####.###.#.#
#.......#...#.#.#...#...#......67890#.....#.#...#.#
###################################################
https://ideone.com/xv2BL3
language:
Java (HotSpot 12)
created:
5 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!